## 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;

}
``````