132 Pattern
Medium · Design · Array · Binary Search · Stack · Monotonic Stack · Ordered Set
Problem
A 132 pattern in an integer array nums is three indices i < j < k with nums[i] < nums[k] < nums[j]: the first value is the smallest, the middle one is the largest, and the last one lies strictly between them (the shape of the digits 1, 3, 2).
Return true if nums contains a 132 pattern, otherwise false.
Examples
Input: nums = [2,5,1,3] Output: true
2, 5, 3 forms the pattern: 2 < 3 < 5 at increasing indices.
Input: nums = [4,3,2,1] Output: false
The array only goes down, so there is never a smaller value before a bigger one.
Input: nums = [1,2,3,4] Output: false
In an increasing array no later value falls between two earlier ones.
Constraints
- n == len(nums)
- 1 <= n <= 2 · 10^5
- -10^9 <= nums[i] <= 10^9
Approaches
- Best "1" for each "3", then scan for the "2" — time O(n²), space O(1)
Follow-up
How would you return the indices of one 132 pattern, not just whether it exists? Keep indices on the stack and remember which "3" popped the current third; when a "1" is found, those three indices form the answer.
Related problems
Start free on Cariara · Coding problems · System design studio
