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