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] <= 109Problem Overview: The task is to determine whether an integer array contains a 132 pattern: three indices i < j < k such that nums[i] < nums[k] < nums[j]. You need to check if there exists a subsequence where the first value is the smallest, the second is the largest, and the third falls strictly between them.
Approach 1: Brute Force (O(n³) time, O(1) space)
The straightforward approach checks every possible triple (i, j, k). Use three nested loops: iterate i from the start, j after i, and k after j. For each combination, verify whether nums[i] < nums[k] < nums[j]. The logic is simple and mirrors the exact definition of the pattern. However, the algorithm performs roughly n³ comparisons, which becomes impractical for large arrays. This method mainly serves as a baseline to confirm understanding of the pattern definition before moving to an optimized approach using a array traversal strategy.
Approach 2: Stack Optimization (O(n) time, O(n) space)
The optimal solution uses a decreasing stack while scanning the array from right to left. The key idea is to track potential candidates for the nums[j] and nums[k] values while searching for a smaller nums[i]. Maintain a variable (often called third) that stores the best candidate for nums[k]. While iterating backward, if the current element is smaller than third, a valid 132 pattern exists.
Otherwise, pop elements from the stack while the current value is greater than the stack top. Each popped value becomes a stronger candidate for nums[k] because it lies between a future larger element and a smaller prefix element. After popping, push the current value onto the stack to maintain a decreasing order. This structure behaves like a monotonic stack, ensuring every element is pushed and popped at most once, giving linear time complexity.
This method works because scanning from the right naturally preserves valid ordering for j and k. The stack keeps possible nums[j] values, while the third variable tracks the largest valid nums[k] discovered so far. The moment you encounter a smaller number to the left, the pattern is confirmed.
Recommended for interviews: Interviewers typically expect the stack-based O(n) approach. The brute force method shows that you understand the pattern definition and constraints, but the optimized solution demonstrates familiarity with monotonic stack techniques and efficient array scanning strategies often used in advanced array problems.
This approach checks all possible triples (i, j, k) to determine if they form a 132 pattern. While straightforward, its complexity can be high for larger arrays due to the triple nested loop structure.
The code iterates over all possible triplets to check if the condition nums[i] < nums[k] < nums[j] holds. If such a triplet is found, it returns true. Otherwise, after all checks, it returns false.
Time complexity: O(n^3) because of the three nested loops.
Space complexity: O(1) since no additional data structures are used.
This approach uses a clever stack-based strategy by scanning the array from right to left. It keeps track of potential '2' and '3' candidates using a stack and a variable, optimizing the search for the '132' pattern.
Iterate from the end of the array to the beginning. The stack is used to keep track of elements greater than a possible '2' in the pattern. 'num3' holds the maximum candidate for '2'.
Time complexity: O(n) because each element is pushed and popped once.
Space complexity: O(n) for the stack.
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force | Time complexity: O(n^3) because of the three nested loops. |
| Approach 2: Stack Optimization | Time complexity: O(n) because each element is pushed and popped once. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triple Loop | O(n³) | O(1) | Useful for understanding the definition of the 132 pattern or verifying small inputs. |
| Monotonic Stack Optimization | O(n) | O(n) | Best choice for interviews and large arrays; scans once using a decreasing stack. |
132 Pattern - Leetcode 456 - Python • NeetCode • 78,478 views views
Watch 9 more video solutions →Practice 132 Pattern with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor