Watch 10 video solutions for Odd Even Jump, a hard level problem involving Array, Dynamic Programming, Stack. This walkthrough by Nick White has 25,497 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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.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.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 * 1040 <= arr[i] < 105Problem Overview: You have an array arr. From index i, odd-numbered jumps must go to the smallest index j > i with arr[j] >= arr[i]. Even-numbered jumps go to the largest index j > i with arr[j] <= arr[i]. A starting index is valid if alternating odd/even jumps eventually reaches the last index. The task is to count how many starting positions work.
Approach 1: Monotonic Stack + Precomputed Jumps (O(n log n) time, O(n) space)
This approach precomputes the next valid index for odd and even jumps using sorting and a monotonic stack. First, sort indices by value (and index for ties) to determine the next greater-or-equal destination for odd jumps. Iterate through the sorted indices while maintaining a stack of increasing indices; whenever the current index is greater than the stack top, pop and record the next jump. Repeat the process with reversed sorting to compute the next smaller-or-equal destination for even jumps.
Once these transitions are known, run dynamic programming from right to left. Maintain two boolean arrays: odd[i] (can reach the end if the next jump is odd) and even[i]. If odd[i] jumps to j, then its value depends on even[j], and vice versa. The last index is trivially reachable. This separation between jump discovery and DP keeps the logic clean and avoids repeated searches.
Approach 2: Dynamic Programming with Ordered Map (O(n log n) time, O(n) space)
This version processes the array from right to left while maintaining an ordered map keyed by values. The map lets you quickly locate the smallest value >= arr[i] for odd jumps and the largest value <= arr[i] for even jumps using ceiling and floor lookups. Languages typically implement this with structures like TreeMap, std::map, or similar ordered sets.
For each index i, query the map to find the candidate indices for the next odd and even jumps. Then update the same two DP states: odd[i] becomes true if the ceiling index leads to a position where even[j] is true, and even[i] becomes true if the floor index leads to a position where odd[j] is true. Insert the current value and index into the ordered structure before moving left. The ordered lookups handle the value constraints efficiently without scanning the suffix.
Recommended for interviews: The monotonic stack solution is the one most interviewers expect. It shows you recognize that jump targets can be precomputed with sorting and stack mechanics instead of repeated searches. The ordered-map DP solution is easier to reason about initially and demonstrates good understanding of array traversal with balanced trees, but the stack-based preprocessing highlights stronger algorithmic insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Monotonic Stack + Precomputed Jumps | O(n log n) | O(n) | Best general solution. Efficiently precomputes next higher/lower jumps using sorting and stack. |
| Dynamic Programming with Ordered Map | O(n log n) | O(n) | Useful when language provides built-in ordered sets like TreeMap or std::map. |