Approach Summary
Traverse right to left with a monotonic-decreasing stack. Pop into k whenever a larger value appears; if nums[i] < k, the 132 pattern exists.
How to Recognize This Pattern
- "Find i < j < k with nums[i] < nums[k] < nums[j]"
- Stack tracks potential "2" (nums[k]) from right to left
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Tags
Array Binary Search Stack Monotonic Stack