Given a sequence of n integers a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list. Note: n will be less than 15,000. Example: Input: [-1, 3, 2, 0] Output: True Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

Example [9, 11, 8, 9, 10]

Step 1 — stack is empty, save pair (9,9)

Step 2 — 11 > stack.peek().min, last pair = stack.pop(), 11 > last.max, last = (9,11), stack is empty, save pair (9,11)

Step 3 — 8 < stack.peek().min, save (8,8)

Step 4 — 9 > stack.peek().min, last = stack.pop(), 9 > last.max, last = (8,9) and does not cover or overlap with stack.peek(), which is (9,11), save (8,9). Stack is now [(9,11), (8,9)]

Step 5 — 10 > stack.peek().min, last = (8,9), 10 > last.max, last = (8,10) and does not cover stack.peek(), which is (9,11). But 10 is in (9,11), return true.

public class Solution { public boolean find132pattern(int[] nums) { Stack<Pair> stack = new Stack(); for (int n : nums) { if (stack.isEmpty() || n < stack.peek().min) { stack.push(new Pair(n,n)); } else if (n > stack.peek().min) { Pair last = stack.pop(); if (n < last.max) return true; else { last.max = n; while (!stack.isEmpty() && last.min <= stack.peek().min && last.max >= stack.peek().max) stack.pop(); // cover previous pair if (!stack.isEmpty() && last.max < stack.peek().max && last.max > stack.peek().min) return true; // overlap with previous pair stack.push(last); } } } return false; } } class Pair { int min; int max; public Pair(int min, int max) { this.min = min; this.max = max; } }