132 Pattern

Head on over here to try the problem for yourself.

This one was so annoying :’(. I ended up following this tutorial for ironing out the final cases.

Algorithm

The goal is to maintain a descending monotonic stack to keep track of the minimum value present before each element in the stack. The ideal case is for the ith index to be as small as possible, the jth index to be as large as possible, and the kth index to be somewhere in between. To keep track of the lowest ith index, we insert into the stack, the smallest element before the current element.

Thats too many words so let’s try an example.

nums[] = [1,4,5,7,8,9,6]
Stack<int[] > st = {}
min = 1
n = nums[1:]
n min st ith jth kth
4 1 {[4,1]} 1 4 ?
5 1 {[5,1]} 1 5 ?
7 1 {[7,1]} 1 7 ?
8 1 {[8,1]} 1 8 ?
9 1 {[9,1]} 1 9 ?
6 1 {[9,1],[6,1]} 1 9 6

We finally get a trio that satisfies so we return true.

Here is a more annoying example.

nums[] = [1,4,0,-1,-2,-3,-1,-2]
n min st ith jth kth
4 1 {[4,1]} 1 4 ?
0 1 {[4,1],[0,1]} 1 4 ?
-1 0 {[4,1],[0,1],[-1,0]} 0 -1 ?
-2 -1 {[4,1],[0,1],[-1,0],[-2,-1]} -1 -2 ?
-3 -2 {[4,1],[0,1],[-1,0],[-2,-1],[-3,-2]} -2 -3 ?
-1 -3 {[4,1],[0,1],[-1,-3]} -3 -1 ?
-2 -3 {[4,1],[0,1],[-1,-3],[-2,-3]} -3 -1 -2

We finally get a trio that satisfies so we return true.

Code

public boolean find132pattern(nums[]) {
  if(nums.length < 3) return false;

  Stack<int[] > st = new Stack();
  int min = nums[0];

  for(int i = 1; i < nums.length; i++) {
    while(!st.empty() && nums[i] >= st.peek()[0]) st.pop();
    if(!st.empty() && nums[i] > st.peek()[1]) return true;
    st.push(new int[] {nums[i], min});
    min = Math.min(min, nums[i]);
  }

  return false;

}