132 Pattern

A brute-force solution checks all triples, but it is O(n^3), so first say that we need to preserve the relative order while avoiding repeated searches. Scan from right to left. Keep a decreasing stack of candidates for the 3 in the pattern, and keep ak, initially negative infinity, as a value that has already been confirmed as the 2: it was popped because a larger value to its left in this reverse scan can serve as the 3. At each number x, if x < ak, we have found x < ak < stackValue, with their original indices ordered i < j < k, so return true. Otherwise pop all stack values smaller than x, assigning each popped value to ak; x can then become a stronger 3, so push it. The stack remains decreasing, and ak is the largest usable 2 seen so far. Use strict comparisons: equal values do not form a 132 pattern. Every element is pushed and popped once, giving O(n) time and O(n) space. Walk through [3, 1, 4, 2]: when processing 4, pop 2 into ak; then 1 is smaller than ak, proving the pattern 1, 4, 2.