132 Pattern
MedPrompt
Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].
Return true if there is a 132 pattern in nums, otherwise, return false.
Example 1:
Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.Example 2:
Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].Example 3:
Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].
Constraints:
n == nums.length1 <= n <= 2 * 105-109 <= nums[i] <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to use three nested loops to check every possible triplet of indices (i, j, k) such that i < j < k. For each triplet, we verify if it forms a 132 pattern, i.e., if nums[i] < nums[k] < nums[j]. If we find such a triplet, we can immediately return true. If we check all possible triplets and don't find one, we return false.
Algorithm
- Iterate through the array with a variable
ifrom0ton-3. - For each
i, iterate with a variablejfromi+1ton-2. - For each
j, iterate with a variablekfromj+1ton-1. - Inside the innermost loop, check if the condition
nums[i] < nums[k] < nums[j]is met. - If the condition is true, a 132 pattern exists, so return
true. - If the loops complete without finding any such triplet, it means no 132 pattern exists. Return
false.
Walkthrough
This method exhaustively searches for the pattern. We use three pointers, i, j, and k, to represent the indices of the three numbers in the potential pattern. The loops are set up to ensure that i < j < k is always true. The outer loop fixes nums[i], the middle loop fixes nums[j], and the inner loop checks all possible nums[k] to see if they satisfy the 132 condition relative to the fixed nums[i] and nums[j].
class Solution { public boolean find132pattern(int[] nums) { int n = nums.length; if (n < 3) { return false; } for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { for (int k = j + 1; k < n; k++) { if (nums[k] > nums[i] && nums[j] > nums[k]) { return true; } } } } return false; }}Complexity
Time
O(n^3) - Three nested loops run through the array, leading to a cubic time complexity. For each of the `O(n)` choices for `i`, there are `O(n)` choices for `j`, and `O(n)` for `k`.
Space
O(1) - Constant extra space is used, as we only need a few variables to store loop indices.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space.
Cons
Extremely inefficient due to its cubic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for input sizes specified in the constraints.
Solutions
Solution
class Solution {public boolean find132pattern(int[] nums) { int vk = -(1 << 30); Deque<Integer> stk = new ArrayDeque<>(); for (int i = nums.length - 1; i >= 0; --i) { if (nums[i] < vk) { return true; } while (!stk.isEmpty() && stk.peek() < nums[i]) { vk = stk.pop(); } stk.push(nums[i]); } return false; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.