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.
This approach leverages a monotonically decreasing stack to precompute odd and even jump indices, allowing future jump calculations to be efficient. We use arrays to track good odd and even jumps. By iterating through the array backwards, we can deduce whether a jump sequence starting from that index is successful. This solution uses a time complexity of O(n log n) due to sorting and precomputation of valid jumps in both odd and even numbered jumps.
Explanation: This implementation creates two arrays, odd and even, to track if an index is reachable from the end with odd or even jumps. It starts by presorting indices for both odd and even conditions (smallest and largest possible jumps). Then it calculates each valid jump using monotonic stacks. A backward iteration is used to fill the odd and even arrays, where respective jump results are determined by the previous position results stored in odd and even, respectively.
Time Complexity: O(n log n), due to sorting of the indices.
Space Complexity: O(n), for storing jump arrays and stacks.
This approach uses a dynamic programming method that leverages sorting and efficient state-tracking to determine if jumping sequences can reach the end. Arrays are used to store information about odd jumps reaching the end, utilizing sorting to precompute the jump possibilities for odd and even stages. This solution effectively uses sorting to handle state transitions in each jump type, further optimized through backward iteration.
Explanation: In this C++ solution, we use a map to track the position of indices that can serve as jumps based on the values they hold. This map is queried with lower and upper boundaries to find valid predecessors and successors. Two boolean vectors, odd and even, store if a jump can successfully reach the end for each index, computed backward with map updates reflecting potential new jump ties.
Time Complexity: O(n log n), due to map operations for insertion and lookup.
Space Complexity: O(n), for map and boolean vectors.
We first use an ordered set to preprocess the positions that can be jumped to from each position, recorded in array g, where g[i][1] and g[i][0] represent the positions that can be jumped to when the current position is an odd jump or an even jump, respectively. If no position can be jumped to, then both g[i][1] and g[i][0] are -1.
Then using memoization search, starting from each position with the current being an odd jump, we determine whether we can jump to the end of the array. If we can, then increment the result by one.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the array.
| Approach | Complexity |
|---|---|
| Monotonic Stack Approach | Time Complexity: O(n log n), due to sorting of the indices. Space Complexity: O(n), for storing jump arrays and stacks. |
| Dynamic Programming with Sorting | Time Complexity: O(n log n), due to map operations for insertion and lookup. Space Complexity: O(n), for map and boolean vectors. |
| Ordered Set + Memoization Search | — |
| 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. |
LeetCode Odd Even Jump Solution Explained - Java • Nick White • 25,497 views views
Watch 9 more video solutions →Practice Odd Even Jump with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor