Watch 10 video solutions for 132 Pattern, a medium level problem involving Array, Binary Search, Stack. This walkthrough by NeetCode has 78,478 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |