LeetCode Q 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].

Solution

The idea is that we can use a stack to keep track of previous min-max intervals.

First we use a array mins[i] to track the min number until ith number.
We use a monotonous decreasing stack stack. In this stack, we store the numbers that are larger than mins[i] in descending order. So whenever we find a number nums[i] > stack.peek(), the 132 pattern is find.

Code

public boolean find132pattern(int[] nums) {
  if (nums == null || nums.length == 0) return false;

  int[] mins = new int[nums.length]; mins[0] = nums[0];
  for (int i = 1; i < nums.length; i++)
  	mins[i] = Math.min(mins[i - 1], nums[i]);

  Deque<Integer> stack = new ArrayDeque<>();

  for (int i = nums.length - 1; i >= 0; i--) {
    if (nums[i] > mins[i]) {
      while (!stack.isEmpty() && stack.peek() <= mins[i])
        stack.pop();
      if (!stack.isEmpty() && stack.peek() < nums[i])
        return true;
      stack.push(nums[i]);
    }
  }

  return false;
}

Reprint policy