forked from varunu28/LeetCode-Java-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path132 Pattern.java
More file actions
25 lines (25 loc) · 727 Bytes
/
132 Pattern.java
File metadata and controls
25 lines (25 loc) · 727 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public boolean find132pattern(int[] nums) {
if (nums.length < 3) {
return false;
}
int[] minTillIndex = new int[nums.length];
minTillIndex[0] = nums[0];
for (int idx = 1; idx < nums.length; idx++) {
minTillIndex[idx] = Math.min(minTillIndex[idx - 1], nums[idx]);
}
Stack<Integer> stack = new Stack<>();
for (int idx = nums.length - 1; idx >= 0; idx--) {
if (nums[idx] > minTillIndex[idx]) {
while (!stack.isEmpty() && stack.peek() <= minTillIndex[idx]) {
stack.pop();
}
if (!stack.isEmpty() && stack.peek() < nums[idx]) {
return true;
}
stack.push(nums[idx]);
}
}
return false;
}
}