2 minutes

# Leetcode 456

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