Odd Even Jump
HardUpdated: Aug 2, 2025
Practice on:
Odd Even Jump Problem
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
jsuch thatarr[i] <= arr[j]andarr[j]is the smallest possible value. If there are multiple such indicesj, you can only jump to the smallest such indexj. - During even-numbered jumps (i.e., jumps 2, 4, 6, ...), you jump to the index
jsuch thatarr[i] >= arr[j]andarr[j]is the largest possible value. If there are multiple such indicesj, you can only jump to the smallest such indexj. - 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.
Examples
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.
Solution
Method 1 – Dynamic Programming with Monotonic Stack
Intuition
To determine from which indices we can reach the end using odd/even jumps, we need to efficiently find the next higher or lower index for each position. We use a monotonic stack and sorting to precompute these jumps, then use dynamic programming to check reachability.
Approach
- For each index, precompute the next higher and next lower index using sorting and a monotonic stack.
- Use two DP arrays:
odd[i]andeven[i]to represent if index i can reach the end with an odd or even jump. - Start from the end and fill DP arrays backwards.
- The answer is the count of indices where
odd[i]is True.
Code
C++
class Solution {
public:
int oddEvenJumps(vector<int>& arr) {
int n = arr.size();
vector<int> next_higher(n, -1), next_lower(n, -1);
vector<pair<int,int>> idx;
for (int i = 0; i < n; ++i) idx.push_back({arr[i], i});
sort(idx.begin(), idx.end());
stack<int> st;
for (auto& [val, i] : idx) {
while (!st.empty() && st.top() < i) {
next_higher[st.top()] = i;
st.pop();
}
st.push(i);
}
idx.clear();
for (int i = 0; i < n; ++i) idx.push_back({-arr[i], i});
sort(idx.begin(), idx.end());
while (!st.empty()) st.pop();
for (auto& [val, i] : idx) {
while (!st.empty() && st.top() < i) {
next_lower[st.top()] = i;
st.pop();
}
st.push(i);
}
vector<bool> odd(n, false), even(n, false);
odd[n-1] = even[n-1] = true;
for (int i = n-2; i >= 0; --i) {
if (next_higher[i] != -1) odd[i] = even[next_higher[i]];
if (next_lower[i] != -1) even[i] = odd[next_lower[i]];
}
return count(odd.begin(), odd.end(), true);
}
};
Go
func oddEvenJumps(arr []int) int {
n := len(arr)
next_higher := make([]int, n)
next_lower := make([]int, n)
for i := range next_higher { next_higher[i], next_lower[i] = -1, -1 }
idx := make([]int, n)
for i := range arr { idx[i] = i }
sort.Slice(idx, func(i, j int) bool { return arr[idx[i]] < arr[idx[j]] || (arr[idx[i]] == arr[idx[j]] && idx[i] < idx[j]) })
st := []int{}
for _, i := range idx {
for len(st) > 0 && st[len(st)-1] < i {
next_higher[st[len(st)-1]] = i
st = st[:len(st)-1]
}
st = append(st, i)
}
idx2 := make([]int, n)
for i := range arr { idx2[i] = i }
sort.Slice(idx2, func(i, j int) bool { return arr[idx2[i]] > arr[idx2[j]] || (arr[idx2[i]] == arr[idx2[j]] && idx2[i] < idx2[j]) })
st = []int{}
for _, i := range idx2 {
for len(st) > 0 && st[len(st)-1] < i {
next_lower[st[len(st)-1]] = i
st = st[:len(st)-1]
}
st = append(st, i)
}
odd := make([]bool, n)
even := make([]bool, n)
odd[n-1], even[n-1] = true, true
for i := n-2; i >= 0; i-- {
if next_higher[i] != -1 { odd[i] = even[next_higher[i]] }
if next_lower[i] != -1 { even[i] = odd[next_lower[i]] }
}
ans := 0
for _, v := range odd {
if v { ans++ }
}
return ans
}
Java
import java.util.*;
class Solution {
public int oddEvenJumps(int[] arr) {
int n = arr.length;
int[] next_higher = new int[n], next_lower = new int[n];
Arrays.fill(next_higher, -1); Arrays.fill(next_lower, -1);
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
Arrays.sort(idx, Comparator.comparingInt(i -> arr[i]));
Stack<Integer> st = new Stack<>();
for (int i : idx) {
while (!st.isEmpty() && st.peek() < i) {
next_higher[st.pop()] = i;
}
st.push(i);
}
Arrays.sort(idx, (i, j) -> arr[j] - arr[i]);
st.clear();
for (int i : idx) {
while (!st.isEmpty() && st.peek() < i) {
next_lower[st.pop()] = i;
}
st.push(i);
}
boolean[] odd = new boolean[n], even = new boolean[n];
odd[n-1] = even[n-1] = true;
for (int i = n-2; i >= 0; i--) {
if (next_higher[i] != -1) odd[i] = even[next_higher[i]];
if (next_lower[i] != -1) even[i] = odd[next_lower[i]];
}
int ans = 0;
for (boolean v : odd) if (v) ans++;
return ans;
}
}
Kotlin
class Solution {
fun oddEvenJumps(arr: IntArray): Int {
val n = arr.size
val next_higher = IntArray(n) { -1 }
val next_lower = IntArray(n) { -1 }
val idx = arr.indices.sortedWith(compareBy({ arr[it] }, { it }))
val st = ArrayDeque<Int>()
for (i in idx) {
while (st.isNotEmpty() && st.last() < i) {
next_higher[st.removeLast()] = i
}
st.addLast(i)
}
val idx2 = arr.indices.sortedWith(compareBy({ -arr[it] }, { it }))
st.clear()
for (i in idx2) {
while (st.isNotEmpty() && st.last() < i) {
next_lower[st.removeLast()] = i
}
st.addLast(i)
}
val odd = BooleanArray(n)
val even = BooleanArray(n)
odd[n-1] = true; even[n-1] = true
for (i in n-2 downTo 0) {
if (next_higher[i] != -1) odd[i] = even[next_higher[i]]
if (next_lower[i] != -1) even[i] = odd[next_lower[i]]
}
return odd.count { it }
}
}
Python
def oddEvenJumps(arr: list[int]) -> int:
n = len(arr)
next_higher = [-1]*n
next_lower = [-1]*n
idx = sorted(range(n), key=lambda i: (arr[i], i))
st = []
for i in idx:
while st and st[-1] < i:
next_higher[st.pop()] = i
st.append(i)
idx2 = sorted(range(n), key=lambda i: (-arr[i], i))
st = []
for i in idx2:
while st and st[-1] < i:
next_lower[st.pop()] = i
st.append(i)
odd = [False]*n
even = [False]*n
odd[-1] = even[-1] = True
for i in range(n-2, -1, -1):
if next_higher[i] != -1:
odd[i] = even[next_higher[i]]
if next_lower[i] != -1:
even[i] = odd[next_lower[i]]
return sum(odd)
Rust
impl Solution {
pub fn odd_even_jumps(arr: Vec<i32>) -> i32 {
let n = arr.len();
let mut next_higher = vec![-1; n];
let mut next_lower = vec![-1; n];
let mut idx: Vec<_> = (0..n).collect();
idx.sort_by_key(|&i| (arr[i], i));
let mut st = Vec::new();
for &i in &idx {
while let Some(&top) = st.last() {
if top < i {
next_higher[top] = i as i32;
st.pop();
} else { break; }
}
st.push(i);
}
idx.sort_by_key(|&i| (-arr[i], i));
st.clear();
for &i in &idx {
while let Some(&top) = st.last() {
if top < i {
next_lower[top] = i as i32;
st.pop();
} else { break; }
}
st.push(i);
}
let mut odd = vec![false; n];
let mut even = vec![false; n];
odd[n-1] = true; even[n-1] = true;
for i in (0..n-1).rev() {
if next_higher[i] != -1 {
odd[i] = even[next_higher[i] as usize];
}
if next_lower[i] != -1 {
even[i] = odd[next_lower[i] as usize];
}
}
odd.iter().filter(|&&x| x).count() as i32
}
}
TypeScript
class Solution {
oddEvenJumps(arr: number[]): number {
const n = arr.length;
const next_higher = Array(n).fill(-1);
const next_lower = Array(n).fill(-1);
const idx = Array.from({length: n}, (_, i) => i).sort((i, j) => arr[i] - arr[j] || i - j);
const st: number[] = [];
for (const i of idx) {
while (st.length && st[st.length-1] < i) {
next_higher[st.pop()!] = i;
}
st.push(i);
}
const idx2 = Array.from({length: n}, (_, i) => i).sort((i, j) => arr[j] - arr[i] || i - j);
st.length = 0;
for (const i of idx2) {
while (st.length && st[st.length-1] < i) {
next_lower[st.pop()!] = i;
}
st.push(i);
}
const odd = Array(n).fill(false);
const even = Array(n).fill(false);
odd[n-1] = even[n-1] = true;
for (let i = n-2; i >= 0; i--) {
if (next_higher[i] !== -1) odd[i] = even[next_higher[i]];
if (next_lower[i] !== -1) even[i] = odd[next_lower[i]];
}
return odd.filter(x => x).length;
}
}
Complexity
- ⏰ Time complexity:
O(n log n), due to sorting and stack operations. - 🧺 Space complexity:
O(n), for DP and jump arrays.