368. 132 Pattern
You are given an integer array nums.
A 132 pattern is a triple of positions i < j < k whose values line up as nums[i] < nums[k] < nums[j] — first a small value, then the largest of the three, then one strictly in between. The three positions do not need to be adjacent.
Return true if nums contains at least one 132 pattern, and false otherwise.
Example 1:
Input: nums = [1, 2, 3, 4]
Output: false
Explanation: The array only ever increases, so a middle-sized value can never appear after the largest one.
Example 2:
Input: nums = [3, 1, 4, 2]
Output: true
Explanation: Positions 1, 2, 3 hold the values 1, 4, 2, and 1 < 2 < 4 — exactly the small → largest → middle shape.
Example 3:
Input: nums = [-1, 3, 2, 0]
Output: true
Explanation: The triple at positions 0, 1, 2 works: −1 < 2 < 3. Several other triples work as well.
Constraints:
- 1 ≤ nums.length ≤ 2 * 10⁵
- -10⁹ ≤ nums[i] ≤ 10⁹
Hints:
Fix the middle position j (the peak of the pattern). The best possible i is whichever index to the left of j holds the smallest value — a running prefix minimum gives you that for free.
For O(n), scan from the right while maintaining a stack kept in decreasing order. Every value the current element pops off is smaller than something to its left — a valid candidate for the pattern's final '2'.
Remember the largest popped value in a variable `third`. The instant you reach an element smaller than `third`, all three roles are filled.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 3, 4]
Expected output: false