TreeMap Flashcards
(Hard) Odd Even Jump
https://leetcode.com/problems/odd-even-jump/
Given an array, make jumps.
During odd jumps you can go to next smallest greater element.
During even jumps you can go to next greatest smaller element.
From how many indexes can you reach the end of the array.
Example 1:
Input: [10,13,12,14,15]
Output: 2
https://leetcode.com/problems/odd-even-jump/discuss/217974/Java-solution-DP-%2B-TreeMap
create a boolean DP array.
dp[i][0] stands for you can arrive index n - 1 starting from index i at an odd step.
dp[i][1] stands for you can arrive index n - 1 starting from index i at an even step.
Result:
Since the first step is odd step, result is count of dp[i][0] with value true.
To quickly find the next greater or smaller number and its index:
traverse the array reversely and store data into a TreeMap using the number as Key and its index as Value.
Time complexity O(nlogn), Space complexity O(n). n is the length of the array.
public int oddEvenJumps(int[] A) {
int n = A.length;
TreeMap\< Integer, Integer\> map = new TreeMap\< \>();
boolean[][] dp = new boolean[n][2];
dp[n - 1][0] = true;
dp[n - 1][1] = true;
map.put(A[n - 1], n - 1);
int res = 1;
for (int i = n - 2; i \> = 0; i--) {
// Odd step
Integer nextGreater = map.ceilingKey(A[i]);
if (nextGreater != null) {
dp[i][0] = dp[map.get(nextGreater)][1];
}
// Even step
Integer nextSmaller = map.floorKey(A[i]);
if (nextSmaller != null) {
dp[i][1] = dp[map.get(nextSmaller)][0];
}
map.put(A[i], i);
res += dp[i][0] ? 1 : 0;
}
return res;
}
