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] < 105#975 Odd Even Jump asks how many starting indices can reach the end of the array if we alternate between odd and even jumps with specific ordering rules. The key insight is to precompute the next valid index for both jump types.
For an odd jump, you must move to the smallest value arr[j] such that arr[j] >= arr[i]. For an even jump, you move to the largest value arr[j] <= arr[i]. Instead of searching every time, we compute these next indices efficiently. A common technique is to sort indices by value and use a monotonic stack to determine the next greater or smaller reachable position. Alternatively, an ordered map/set (like TreeMap) can track candidates while scanning.
Once the next jump targets are known, apply dynamic programming where dp[i][0] and dp[i][1] track whether reaching the end is possible with an even or odd jump from index i. The algorithm runs in roughly O(n log n) time with O(n) space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Monotonic Stack + Dynamic Programming | O(n log n) | O(n) |
| Ordered Map (TreeMap) + Dynamic Programming | O(n log n) | O(n) |
Striver
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Odd Even Jump is considered a challenging problem that tests knowledge of ordered structures, monotonic stacks, and dynamic programming. Variations of this problem or its techniques often appear in high-level technical interviews.
The optimal approach precomputes the next valid index for odd and even jumps using sorting with a monotonic stack or an ordered map. After determining these transitions, dynamic programming is used to track whether each index can reach the end.
Dynamic programming helps determine whether reaching the end is possible from each index depending on the jump type. By working backward and using precomputed next jumps, we avoid recomputation and efficiently track reachable states.
Common choices include a monotonic stack combined with sorted indices or an ordered set/map like TreeMap. These structures help efficiently determine the next greater or next smaller index required for odd and even jumps.