forked from varunu28/LeetCode-Java-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathOdd Even Jump.java
More file actions
33 lines (33 loc) · 1.1 KB
/
Odd Even Jump.java
File metadata and controls
33 lines (33 loc) · 1.1 KB
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
33
class Solution {
public int oddEvenJumps(int[] A) {
if (A.length <= 1) {
return A.length;
}
boolean[] odd = new boolean[A.length];
boolean[] even = new boolean[A.length];
odd[A.length - 1] = even[A.length - 1] = true;
TreeMap<Integer, Integer> treeMap = new TreeMap<>();
treeMap.put(A[A.length - 1], A.length - 1);
int count = 0;
for (int i = A.length - 2; i >= 0; i--) {
int val = A[i];
if (treeMap.containsKey(val)) {
odd[i] = even[treeMap.get(val)];
even[i] = odd[treeMap.get(val)];
}
else {
Integer lower = treeMap.lowerKey(val);
Integer higher = treeMap.higherKey(val);
if (lower != null) {
even[i] = odd[treeMap.get(lower)];
}
if (higher != null) {
odd[i] = even[treeMap.get(higher)];
}
}
treeMap.put(val, i);
count += odd[i] ? 1 : 0;
}
return count + 1;
}
}