456. 132 Pattern

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 1:

Input: [1, 2, 3, 4]

Output: False

Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: [3, 1, 4, 2]

Output: True

Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

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].
  • Monotonic Stack
    • k is ak, is “2” in “132”
    • elements in the stack are valid “3” in “132”
    • the while loop increases both “3” and “2”

public boolean find132pattern(int[] nums) {
    Stack<Integer> stack = new Stack<>();
    int k = Integer.MIN_VALUE;
    for(int i = nums.length-1; i >= 0; i--) {
        int v = nums[i];
        if(v < k) return true;
        while(!stack.isEmpty() && v > stack.peek()) {
            k = stack.pop(); // this is a better ak < aj pair
        }
        stack.push(v);
    }
    return false;
}
  • TreeSet

class Solution {
    public boolean find132pattern(int[] nums) {
        if(nums.length < 3) return false;
        int[] mins = new int[nums.length];
        mins[1] = nums[0];
        for(int i = 2; i < nums.length; i++)
            mins[i] = Math.min(nums[i-1], mins[i-1]);
        TreeSet<Integer> set = new TreeSet<>();
        for(int i = nums.length-1; i >= 1; i--) {
            int min = mins[i];
            int max = nums[i];

            if(min < max && !set.subSet(min, false, max, false).isEmpty()) {
                return true;
            }
            set.add(max);
        }
        return false;
    }
}