# Odd Even Jump
**Difficulty:** HARD
[External](https://leetcode.com/problems/odd-even-jump)
Canonical: https://scaleengineer.com/dsa/problems/odd-even-jump
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Stack, Monotonic Stack, Ordered Set
---
## Problem
You are given an integer array `arr`. From some starting index, you can make a series of jumps. The (1st, 3rd, 5th, ...) jumps in the series are called **odd-numbered jumps**, and the (2nd, 4th, 6th, ...) jumps in the series are called **even-numbered jumps**. Note that the **jumps** are numbered, not the indices.

You may jump forward from index `i` to index `j` (with `i < j`) in the following way:

* During **odd-numbered jumps** (i.e., jumps 1, 3, 5, ...), you jump to the index `j` such that `arr[i] <= arr[j]` and `arr[j]` is the smallest possible value. If there are multiple such indices `j`, you can only jump to the **smallest** such index `j`.
* During **even-numbered jumps** (i.e., jumps 2, 4, 6, ...), you jump to the index `j` such that `arr[i] >= arr[j]` and `arr[j]` is the largest possible value. If there are multiple such indices `j`, you can only jump to the **smallest** such index `j`.
* It may be the case that for some index `i`, there are no legal jumps.

A starting index is **good** if, starting from that index, you can reach the end of the array (index `arr.length - 1`) by jumping some number of times (possibly 0 or more than once).

Return _the number of **good** starting indices_.

**Example 1:**

**Input:** arr = [10,13,12,14,15]
**Output:** 2
**Explanation:** 
From starting index i = 0, we can make our 1st jump to i = 2 (since arr[2] is the smallest among arr[1], arr[2], arr[3], arr[4] that is greater or equal to arr[0]), then we cannot jump any more.
From starting index i = 1 and i = 2, we can make our 1st jump to i = 3, then we cannot jump any more.
From starting index i = 3, we can make our 1st jump to i = 4, so we have reached the end.
From starting index i = 4, we have reached the end already.
In total, there are 2 different starting indices i = 3 and i = 4, where we can reach the end with some number of
jumps.

**Example 2:**

**Input:** arr = [2,3,1,1,4]
**Output:** 3
**Explanation:** 
From starting index i = 0, we make jumps to i = 1, i = 2, i = 3:
During our 1st jump (odd-numbered), we first jump to i = 1 because arr[1] is the smallest value in [arr[1], arr[2], arr[3], arr[4]] that is greater than or equal to arr[0].
During our 2nd jump (even-numbered), we jump from i = 1 to i = 2 because arr[2] is the largest value in [arr[2], arr[3], arr[4]] that is less than or equal to arr[1]. arr[3] is also the largest value, but 2 is a smaller index, so we can only jump to i = 2 and not i = 3
During our 3rd jump (odd-numbered), we jump from i = 2 to i = 3 because arr[3] is the smallest value in [arr[3], arr[4]] that is greater than or equal to arr[2].
We can't jump from i = 3 to i = 4, so the starting index i = 0 is not good.
In a similar manner, we can deduce that:
From starting index i = 1, we jump to i = 4, so we reach the end.
From starting index i = 2, we jump to i = 3, and then we can't jump anymore.
From starting index i = 3, we jump to i = 4, so we reach the end.
From starting index i = 4, we are already at the end.
In total, there are 3 different starting indices i = 1, i = 3, and i = 4, where we can reach the end with some
number of jumps.

**Example 3:**

**Input:** arr = [5,1,3,4,2]
**Output:** 3
**Explanation:** We can reach the end from starting indices 1, 2, and 4.

**Constraints:**

* `1 <= arr.length <= 2 * 104`
* `0 <= arr[i] < 105`

# Approaches
## Brute Force with Dynamic Programming
This approach uses dynamic programming by working backward from the end of the array. For each index `i`, we determine if it's possible to reach the end starting with an odd jump (`odd[i]`) or an even jump (`even[i]`). To find the next jump from `i`, we perform a linear scan through the rest of the array, which is a brute-force method.
**Time:** O(N^2), where N is the number of elements in the array. The main loop runs N times, and inside it, we perform two linear scans of the subarray to the right, which takes up to O(N) time. · **Space:** O(N), where N is the number of elements in the array. This is for the `odd` and `even` DP arrays.
**Pros:** The logic is straightforward and relatively easy to understand and implement.
**Cons:** The `O(N^2)` time complexity makes it too slow for the given constraints, leading to a Time Limit Exceeded (TLE) error on larger test cases.
### Explanation
We define two boolean arrays, `odd` and `even`, of the same size as the input array `arr`. `odd[i]` is true if we can reach the last index starting from `i` with an odd-numbered jump. `even[i]` is true if we can reach the last index starting from `i` with an even-numbered jump.

The base case is the last index, `n-1`. Since we are already at the end, both `odd[n-1]` and `even[n-1]` are true.

We iterate from `i = n-2` down to `0`. For each `i`:
*   To calculate `odd[i]`, we need to find the destination `j` of the next (odd) jump. This involves searching all indices `k > i` to find one where `arr[k] >= arr[i]` and `arr[k]` is minimized. If multiple such `k` exist, the smallest `k` is chosen. If such a `j` is found, `odd[i]` becomes `even[j]`, because the next jump from `j` will be an even jump. If no such `j` exists, `odd[i]` is false.
*   Similarly, to calculate `even[i]`, we find the destination `k` of the next (even) jump. This requires finding an index `l > i` where `arr[l] <= arr[i]` and `arr[l]` is maximized. If a tie occurs, the smallest `l` is chosen. If such a `k` is found, `even[i]` becomes `odd[k]`. Otherwise, `even[i]` is false.

The search for the next jump target for each `i` takes `O(n-i)` time. Finally, the total number of good starting indices is the count of `true` values in the `odd` array, since the first jump is always an odd jump.

```java
class Solution {
    public int oddEvenJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) {
            return n;
        }

        boolean[] odd = new boolean[n];
        boolean[] even = new boolean[n];
        odd[n - 1] = true;
        even[n - 1] = true;

        int goodIndices = 1; // The last index is always a good starting point

        for (int i = n - 2; i >= 0; i--) {
            // Find next odd jump
            int oddNextJump = -1;
            int minValOdd = Integer.MAX_VALUE;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] >= arr[i]) {
                    if (arr[j] < minValOdd) {
                        minValOdd = arr[j];
                        oddNextJump = j;
                    }
                }
            }

            // Find next even jump
            int evenNextJump = -1;
            int maxValEven = Integer.MIN_VALUE;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] <= arr[i]) {
                    if (arr[j] > maxValEven) {
                        maxValEven = arr[j];
                        evenNextJump = j;
                    }
                }
            }

            if (oddNextJump != -1) {
                odd[i] = even[oddNextJump];
            }
            if (evenNextJump != -1) {
                even[i] = odd[evenNextJump];
            }

            if (odd[i]) {
                goodIndices++;
            }
        }

        return goodIndices;
    }
}
```
### Algorithm
*   Initialize `n` as the length of the input array `arr`.
*   Create two boolean arrays, `odd` and `even`, of size `n` to store the dynamic programming states.
*   The base case is the last index. Since it's the target, we can reach it from itself. So, set `odd[n-1] = true` and `even[n-1] = true`.
*   Iterate backwards from `i = n - 2` down to `0`.
*   For each index `i`:
    *   To find the next odd jump target, iterate from `j = i + 1` to `n - 1`. Keep track of the best candidate index `oddNextJump` that corresponds to the minimum `arr[j]` such that `arr[j] >= arr[i]`. The tie-breaking rule (smallest index) is naturally handled by not updating the target if a value equal to the current minimum is found at a larger index.
    *   If a valid `oddNextJump` is found, set `odd[i] = even[oddNextJump]`.
    *   Similarly, to find the next even jump target, iterate from `j = i + 1` to `n - 1`. Find the best candidate `evenNextJump` corresponding to the maximum `arr[j]` such that `arr[j] <= arr[i]`.
    *   If a valid `evenNextJump` is found, set `even[i] = odd[evenNextJump]`.
*   After filling the DP arrays, count the number of `true` values in the `odd` array. This is the result, as the first jump from any starting index is an odd-numbered jump.

## Dynamic Programming with TreeMap
This approach improves upon the brute-force DP by optimizing the search for the next jump target. Instead of a linear scan, it uses a `TreeMap` (a balanced binary search tree) to find the next valid jump in logarithmic time, leading to an overall `O(N log N)` time complexity.
**Time:** O(N log N), where N is the number of elements. The loop runs N times, and each `TreeMap` operation (`ceilingEntry`, `floorEntry`, `put`) takes `O(log k)` time, where `k` is the current size of the map. The total time is the sum of `log(1) + log(2) + ... + log(N-1)`, which is `O(N log N)`. · **Space:** O(N), where N is the number of elements. The `TreeMap` can store up to N entries, and we use two DP arrays of size N.
**Pros:** Highly efficient with `O(N log N)` time complexity, which passes the given constraints.; It's a standard and elegant way to solve problems requiring ordered statistics on a dynamically growing set of elements.
**Cons:** The implementation is more complex than the brute-force approach due to the use of a `TreeMap`.; The constant factor for `log N` operations might be larger than other `O(N log N)` solutions like sorting, though asymptotically they are equivalent.
### Explanation
The core DP logic remains the same: we compute `odd[i]` and `even[i]` by working backward from the end of the array. The key improvement is how we find the next jump targets.

We use a `TreeMap` to store `(value, index)` pairs for the elements we have processed so far (i.e., for indices `k > i`). The map is keyed by `arr[k]` and the value is `k`.

We iterate `i` from `n-2` down to `0`. At each step `i`, the `TreeMap` contains information about `arr[i+1...n-1]`.
*   To find the odd jump target from `i`: We need the smallest `arr[j] >= arr[i]` for `j > i`. This is equivalent to finding the ceiling key for `arr[i]` in our `TreeMap`. The `ceilingEntry(arr[i])` method gives us the entry with the smallest key greater than or equal to `arr[i]`. The value of this entry is our target index `j`. Then, `odd[i] = even[j]`.
*   To find the even jump target from `i`: We need the largest `arr[j] <= arr[i]` for `j > i`. This is equivalent to finding the floor key for `arr[i]`. The `floorEntry(arr[i])` method gives us the entry with the largest key less than or equal to `arr[i]`. The value of this entry is our target index `k`. Then, `even[i] = odd[k]`.

After processing index `i`, we add `(arr[i], i)` to the `TreeMap`. If a key `arr[i]` already exists, we overwrite its value with `i`. Since we iterate `i` downwards, this ensures that for any value, the map always stores the smallest index, correctly handling the tie-breaking rule.

The total count of good starting indices is the sum of `true` values in the `odd` array.

```java
import java.util.TreeMap;
import java.util.Map;

class Solution {
    public int oddEvenJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) {
            return n;
        }

        boolean[] odd = new boolean[n];
        boolean[] even = new boolean[n];
        odd[n - 1] = true;
        even[n - 1] = true;

        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(arr[n - 1], n - 1);

        int goodIndices = 1;

        for (int i = n - 2; i >= 0; i--) {
            // Find odd jump (ceiling)
            Map.Entry<Integer, Integer> oddJumpEntry = map.ceilingEntry(arr[i]);
            if (oddJumpEntry != null) {
                odd[i] = even[oddJumpEntry.getValue()];
            }

            // Find even jump (floor)
            Map.Entry<Integer, Integer> evenJumpEntry = map.floorEntry(arr[i]);
            if (evenJumpEntry != null) {
                even[i] = odd[evenJumpEntry.getValue()];
            }

            if (odd[i]) {
                goodIndices++;
            }

            // Add current element to the map for subsequent iterations
            // If value exists, it's updated with the smaller index i
            map.put(arr[i], i);
        }

        return goodIndices;
    }
}
```
### Algorithm
*   Initialize `n` as the length of `arr`.
*   Create boolean arrays `odd[n]` and `even[n]`. Set `odd[n-1] = true` and `even[n-1] = true`.
*   Initialize a `TreeMap<Integer, Integer>` named `map` to store `(value, index)` pairs. The `TreeMap` will keep these pairs sorted by `value`.
*   Add the last element to the map: `map.put(arr[n-1], n-1)`.
*   Iterate backwards from `i = n - 2` down to `0`.
*   For each `i`:
    *   To find the odd jump target, search for the smallest key in `map` that is greater than or equal to `arr[i]`. This can be done using `map.ceilingEntry(arr[i])`. If an entry is found, its value is the index `j` of the next jump. We then set `odd[i] = even[j]`.
    *   To find the even jump target, search for the largest key in `map` that is less than or equal to `arr[i]`. This is done using `map.floorEntry(arr[i])`. If an entry is found, its value is the index `k` of the next jump. We then set `even[i] = odd[k]`.
    *   After processing `i`, add its value and index to the map: `map.put(arr[i], i)`. Since we iterate `i` downwards, if a value `arr[i]` already exists as a key, this update ensures the map stores the smallest index for that value, correctly handling the tie-breaker rule.
*   Count the number of `true` values in the `odd` array to get the final answer.

# Solutions
### Java

```java
class Solution {
private
  int n;
private
  Integer[][] f;
private
  int[][] g;
public
  int oddEvenJumps(int[] arr) {
    TreeMap<Integer, Integer> tm = new TreeMap<>();
    n = arr.length;
    f = new Integer[n][2];
    g = new int[n][2];
    for (int i = n - 1; i >= 0; --i) {
      var hi = tm.ceilingEntry(arr[i]);
      g[i][1] = hi == null ? -1 : hi.getValue();
      var lo = tm.floorEntry(arr[i]);
      g[i][0] = lo == null ? -1 : lo.getValue();
      tm.put(arr[i], i);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans += dfs(i, 1);
    }
    return ans;
  }
private
  int dfs(int i, int k) {
    if (i == n - 1) {
      return 1;
    }
    if (g[i][k] == -1) {
      return 0;
    }
    if (f[i][k] != null) {
      return f[i][k];
    }
    return f[i][k] = dfs(g[i][k], k ^ 1);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int oddEvenJumps(vector<int> &arr) {
    int n = arr.size();
    map<int, int> d;
    int f[n][2];
    int g[n][2];
    memset(f, 0, sizeof(f));
    for (int i = n - 1; ~i; --i) {
      auto it = d.lower_bound(arr[i]);
      g[i][1] = it == d.end() ? -1 : it->second;
      it = d.upper_bound(arr[i]);
      g[i][0] = it == d.begin() ? -1 : prev(it)->second;
      d[arr[i]] = i;
    }
    function<int(int, int)> dfs = [&](int i, int k) -> int {
      if (i == n - 1) {
        return 1;
      }
      if (g[i][k] == -1) {
        return 0;
      }
      if (f[i][k] != 0) {
        return f[i][k];
      }
      return f[i][k] = dfs(g[i][k], k ^ 1);
    };
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans += dfs(i, 1);
    }
    return ans;
  }
};

```

### Python

```python
from sortedcontainers import SortedDict class Solution : def oddEvenJumps ( self , arr : List [ int ]) -> int : @ cache def dfs ( i : int , k : int ) -> bool : if i == n - 1 : return True if g [ i ][ k ] == - 1 : return False return dfs ( g [ i ][ k ], k ^ 1 ) n = len ( arr ) g = [[ 0 ] * 2 for _ in range ( n )] sd = SortedDict () for i in range ( n - 1 , - 1 , - 1 ): j = sd . bisect_left ( arr [ i ]) g [ i ][ 1 ] = sd . values ()[ j ] if j < len ( sd ) else - 1 j = sd . bisect_right ( arr [ i ]) - 1 g [ i ][ 0 ] = sd . values ()[ j ] if j >= 0 else - 1 sd [ arr [ i ]] = i return sum ( dfs ( i , 1 ) for i in range ( n ))
```