-
Notifications
You must be signed in to change notification settings - Fork 0
/
132 pattern
32 lines (26 loc) · 1.02 KB
/
132 pattern
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
26
27
28
29
30
31
32
public boolean find132pattern(int[] nums) {
int[] min=nums.clone();
for(int i=1; i<min.length; i++){
min[i]=Math.min(min[i], min[i-1]);
}
// System.out.println(Arrays.toString(min));
TreeSet<Integer> set=new TreeSet<>();
for(int i=nums.length-1; i>0; i--){
int num=nums[i];
if(set.lower(num)!=null){
int left=min[i-1];
int right=set.lower(num);
// System.out.println(left+"left");
// System.out.println(right+"right");
if(left<right) {
// System.out.println("true");
return true;
}
}
set.add(num);
}
return false;
}
}
#Status: i would have taken the naive approach to run 2 loops and make it O(n*n), but since the question asked for o(logn) complexity, i searched for optimal solution.
Had to debug at different points. Learned about treesets.