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.
We can improve upon the brute-force approach by optimizing the search for the first element of the pattern (nums[i]). Instead of iterating through all possible i for each j, we can observe that for a fixed nums[j], the condition nums[i] < nums[k] < nums[j] is easiest to satisfy if nums[i] is the smallest possible value. Therefore, for each j, we only need to consider the minimum value in the subarray nums[0...j-1] as our nums[i] candidate. This reduces one of the loops.
Algorithm
- We fix the middle element of the pattern,
nums[j](the '3'). - We iterate
jfrom1ton-1. - For each
j, we need to find an elementnums[i]to its left (i < j) that is as small as possible. We can maintain a variableleftMinthat stores the minimum value innums[0...j-1]. - Then, for the fixed
jandleftMin, we search for an elementnums[k]to the right ofj(k > j). - We iterate
kfromj+1ton-1. - If we find a
nums[k]such thatleftMin < nums[k] < nums[j], we have found the pattern and returntrue. - If the loops complete, we return
false.
Walkthrough
In this approach, we iterate through the array with an index j, considering nums[j] as the '3' in the '132' pattern. For each j, we need to find a '1' (nums[i]) to its left and a '2' (nums[k]) to its right. The best candidate for nums[i] is the minimum element to the left of j. We can find this minimum in O(1) time for each j by pre-calculating it or by maintaining a running minimum as we iterate. Then, we perform a linear scan to the right of j to find a nums[k] that fits between our nums[i] (the left minimum) and nums[j].
class Solution { public boolean find132pattern(int[] nums) { int n = nums.length; if (n < 3) { return false; } int leftMin = nums[0]; for (int j = 1; j < n - 1; j++) { // Update leftMin to be the minimum of elements before index j leftMin = Math.min(leftMin, nums[j-1]); for (int k = j + 1; k < n; k++) { if (nums[k] > leftMin && nums[k] < nums[j]) { return true; } } } return false; }}Note: The leftMin update in the code above is slightly off for the first iteration but works. A cleaner way is to calculate leftMin for nums[0...j-1] before the inner loop, or precompute a min array.
Complexity
Time
O(n^2) - We have a nested loop structure. The outer loop runs from `j=1` to `n-1`, and the inner loop runs from `k=j+1` to `n-1`. This results in a quadratic time complexity.
Space
O(1) - We only need one extra variable, `leftMin`, to keep track of the minimum element to the left.
Trade-offs
Pros
A significant improvement over the O(n^3) approach.
Uses constant extra space if we calculate the minimum on the fly.
Cons
The time complexity is still quadratic, which is too slow for the given constraints and will likely time out.
The most efficient solution involves a single pass through the array and the use of a stack. By traversing the array from right to left, we can efficiently track potential candidates for the '2' and '3' elements of the pattern. Let's denote the pattern elements as s1, s3, s2 corresponding to nums[i], nums[j], nums[k]. We are looking for s1 < s2 < s3 with their original indices being i < j < k.
When we iterate from right to left, at any point i, the current element nums[i] can be our s1. We just need to know if there's a pair (s3, s2) to its right (at indices j, k > i) such that s1 < s2 < s3. The stack helps us maintain a pool of s3 candidates, and a variable s2 tracks the best (largest) s2 value found so far for a (s3, s2) pair to the right.
Algorithm
- We are looking for indices
i < j < ksuch thatnums[i] < nums[k] < nums[j]. - Let's name
nums[i]ass1,nums[j]ass3, andnums[k]ass2. The condition iss1 < s2 < s3. - We iterate through the array from right to left.
- We use a stack to keep track of potential
s3candidates. - We use a variable, let's call it
s2, to store the largest possible value for ans2candidate found so far. Initializes2to negative infinity. - For each element
nums[i]from right to left:- If
nums[i] < s2, we have found ours1.nums[i]iss1,s2is ours2, and thes3that produced thiss2has already been processed (it's an element larger thans2that we encountered to the right). Thus, a 132 pattern exists, and we returntrue. - We then update the stack and
s2. While the stack is not empty andnums[i]is greater than the element at the top of the stack, it meansnums[i]can act as a betters3for thes2candidate atstack.peek(). So we pop from the stack and updates2to be this popped element, as it's a valids2for thes3candidatenums[i]. - After the while loop, we push
nums[i]onto the stack. It becomes a candidate fors3for the elements we will process to its left.
- If
Walkthrough
We initialize a variable s2 to a very small number and an empty stack. We iterate from the end of the array to the beginning. For each element nums[i], we first check if it's smaller than s2. If it is, we've found our s1 (nums[i]), and we already have an s2 and an implicit s3 to its right, so we return true.
If nums[i] is not smaller than s2, we use it to update our s2 and stack. The stack stores elements that are potential s3 candidates. We pop elements from the stack as long as they are smaller than the current nums[i]. Each popped element is a potential s2, and since we want the largest possible s2, we update s2 = popped_element. After this, nums[i] is pushed onto the stack, becoming a candidate for s3 for the elements to its left.
This works because the stack maintains a decreasing sequence of numbers. When we find a nums[i] larger than the stack's top, nums[i] can be an s3 and the stack's top can be an s2. By popping all smaller elements, we find the largest possible s2 for the s3 formed by nums[i] and other elements on the stack.
import java.util.Stack; class Solution { public boolean find132pattern(int[] nums) { int n = nums.length; if (n < 3) { return false; } Stack<Integer> stack = new Stack<>(); int s2 = Integer.MIN_VALUE; // This will store the '2' in 132 pattern for (int i = n - 1; i >= 0; i--) { // Check if we found the '1' of the pattern if (nums[i] < s2) { return true; } // Maintain stack and update s2 // nums[i] is a candidate for '3' while (!stack.isEmpty() && nums[i] > stack.peek()) { // stack.peek() is a candidate for '2' s2 = stack.pop(); } // Push current element as a candidate for '3' stack.push(nums[i]); } return false; }}Complexity
Time
O(n) - We traverse the array once. Each element is pushed and popped from the stack at most once. Therefore, the total time spent on stack operations across all iterations is proportional to `n`.
Space
O(n) - In the worst case (e.g., a strictly decreasing array), the stack might store all `n` elements.
Trade-offs
Pros
Optimal O(n) time complexity.
Solves the problem efficiently for large inputs.
An elegant application of the monotonic stack data structure.
Cons
The logic can be non-intuitive and tricky to devise under pressure.
Requires extra space for the stack.
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; }}class Solution {public: bool find132pattern(vector<int> &nums) { int vk = INT_MIN; stack<int> stk; for (int i = nums.size() - 1; ~i; --i) { if (nums[i] < vk) { return true; } while (!stk.empty() && stk.top() < nums[i]) { vk = stk.top(); stk.pop(); } stk.push(nums[i]); } return false; }};class Solution: def find132pattern(self, nums: List[int]) -> bool: vk = - inf stk = [] for x in nums[:: - 1]: if x < vk: return True while stk and stk[- 1] < x: vk = stk . pop() stk . append(x) return FalseVideo 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.