DSA problem
132 Pattern
Given an array of n integers nums, a 132 pattern is a subsequence of three indices i < j < k such that nums[i] < nums[k] < nums[j]. Return true if such a triple exists, otherwise false.
A naive triple-nested loop is O(n³); even fixing j and scanning for valid i and k is O(n²). For n up to 2 * 10⁵ we need a near-linear algorithm.
The clever insight is to iterate from right to left and use a monotonic decreasing stack to track potential "2" values (i.e., nums[j] candidates). At each step we maintain a variable secondMax representing the largest value that has been popped off the stack — this is a valid nums[k] because it appears to the right of the current index and is smaller than something else still on the stack. If at any point the current value nums[i] is strictly less than secondMax, we have found a 132 pattern.
Concretely: scan i from n - 1 down to 0. If nums[i] < secondMax, return true. Otherwise, while the stack is non-empty and nums[i] > stack.top, pop and update secondMax = max(secondMax, popped). Push nums[i]. The total work is O(n) because each element is pushed and popped at most once, and the secondMax variable encodes the "best valid k" without needing to enumerate it.
Examples
nums = [1,2,3,4]falsenums = [3,1,4,2]truenums = [-1,3,2,0]trueConstraints
- n == nums.length
- 1 <= n <= 2 * 10^5
- -10^9 <= nums[i] <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.