Odd Even Jump

Hard
1092.

Odd Even Jump

Odd Even Jump is a hard coding problem on arrays, dynamic programming and stack, asked in Amazon, Google, Meta and Sprinklr interviews.

From index i you may jump forward. Jumps are numbered from 1, and:

  • on an odd-numbered jump you move to the smallest index j > i such that arr[j] is the smallest value that is at least arr[i];
  • on an even-numbered jump you move to the smallest index j > i such that arr[j] is the largest value that is at most arr[i].

If no such j exists the jump cannot be made. An index is good if, starting there, you can reach the last index by some sequence of jumps.

Return the number of good starting indices.

Example 1

Input
arr = [10,13,12,14,15]
Output
2
Explanation
Only indices 3 and 4 work.

Example 2

Input
arr = [2,3,1,1,4]
Output
3
Explanation
Indices 1, 3 and 4.

Example 3

Input
arr = [5,1,3,4,2]
Output
3
Explanation
Indices 1, 2 and 4.

Constraints

  • 1 <= arr.length <= 2 * 10^4
  • 0 <= arr[i] < 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var oddEvenJumps = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Odd Even Jump — Solution in Python, Java & C++

Odd Even Jump solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.

Odd Even Jump is a hard coding problem on arrays, dynamic programming and stack, asked in Amazon, Google, Meta and Sprinklr interviews.

Problem statement

From index i you may jump forward. Jumps are numbered from 1, and:

  • on an odd-numbered jump you move to the smallest index j > i such that arr[j] is the smallest value that is at least arr[i];
  • on an even-numbered jump you move to the smallest index j > i such that arr[j] is the largest value that is at most arr[i].

If no such j exists the jump cannot be made. An index is good if, starting there, you can reach the last index by some sequence of jumps.

Return the number of good starting indices.

Example 1

Input: arr = [10,13,12,14,15]
Output: 2
Explanation: Only indices 3 and 4 work.

Example 2

Input: arr = [2,3,1,1,4]
Output: 3
Explanation: Indices 1, 3 and 4.

Example 3

Input: arr = [5,1,3,4,2]
Output: 3
Explanation: Indices 1, 2 and 4.

Constraints

  • 1 <= arr.length <= 2 * 10^4
  • 0 <= arr[i] < 10^5

Hints for Odd Even Jump

  1. Hint 1

    Work backwards: the last index is good, and whether i is good depends only on where its next jump lands.

  2. Hint 2

    You need two arrays: for each i, the target of an odd jump and the target of an even jump.

  3. Hint 3

    Both come from a monotonic stack over the indices sorted by value — ascending for odd jumps, descending for even.

How to solve Odd Even Jump

Precompute nextHigher[i] and nextLower[i] — where an odd and an even jump from i land — then sweep backwards. odd[i] is true when an odd jump from i reaches a position that is good on an even jump, and vice versa; the last index is good on both.

Approach

  1. Sort the indices by (value, index) ascending; a monotonic stack over that order yields nextHigher.
  2. Sort by (value descending, index ascending); the same stack pass yields nextLower.
  3. Set odd[n-1] = even[n-1] = true.
  4. For i from n-2 down: odd[i] = even[nextHigher[i]] and even[i] = odd[nextLower[i]] where the targets exist.
  5. Count the true entries of odd.

Why it works

The tie-breaks are why the sorts differ: an odd jump wants the smallest qualifying value and then the smallest index, which is exactly the (value, index) order; an even jump wants the largest value and then the smallest index, which is (−value, index). The stack pass turns each order into "next greater index" in linear time, and the parity alternation is what forces two boolean arrays rather than one.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Odd and even jumps swap roles at each step, so the recurrence crosses between the two arrays.
  • Both jump kinds require a later index; equal values at an earlier index do not count.
  • The last index is good regardless of parity and seeds the whole sweep.

Reference solution

Python

from typing import List

def oddEvenJumps(arr: List[int]) -> int:
    n = len(arr)

    def make_next(order):
        res = [-1] * n
        stack = []
        for i in order:
            while stack and i > stack[-1]:
                res[stack.pop()] = i
            stack.append(i)
        return res

    asc = sorted(range(n), key=lambda i: (arr[i], i))
    desc = sorted(range(n), key=lambda i: (-arr[i], i))
    next_higher = make_next(asc)
    next_lower = make_next(desc)
    odd = [False] * n
    even = [False] * n
    odd[n - 1] = even[n - 1] = True
    count = 1
    for i in range(n - 2, -1, -1):
        if next_higher[i] >= 0:
            odd[i] = even[next_higher[i]]
        if next_lower[i] >= 0:
            even[i] = odd[next_lower[i]]
        if odd[i]:
            count += 1
    return count

Java

public static int oddEvenJumps(int[] arr) {
    int n = arr.length;
    Integer[] asc = new Integer[n];
    Integer[] desc = new Integer[n];
    for (int i = 0; i < n; i++) {
        asc[i] = i;
        desc[i] = i;
    }
    Arrays.sort(asc, (a, b) -> arr[a] != arr[b] ? arr[a] - arr[b] : a - b);
    Arrays.sort(desc, (a, b) -> arr[a] != arr[b] ? arr[b] - arr[a] : a - b);
    int[] nextHigher = oejNext(asc, n);
    int[] nextLower = oejNext(desc, n);
    boolean[] odd = new boolean[n];
    boolean[] even = new boolean[n];
    odd[n - 1] = true;
    even[n - 1] = true;
    int count = 1;
    for (int i = n - 2; i >= 0; i--) {
        if (nextHigher[i] >= 0) odd[i] = even[nextHigher[i]];
        if (nextLower[i] >= 0) even[i] = odd[nextLower[i]];
        if (odd[i]) count++;
    }
    return count;
}

private static int[] oejNext(Integer[] order, int n) {
    int[] res = new int[n];
    Arrays.fill(res, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    for (int idx : order) {
        while (!stack.isEmpty() && idx > stack.peek()) res[stack.pop()] = idx;
        stack.push(idx);
    }
    return res;
}

C++

static vector<int> oejNext(vector<int>& order, int n) {
    vector<int> res(n, -1);
    vector<int> stack;
    for (int idx : order) {
        while (!stack.empty() && idx > stack.back()) {
            res[stack.back()] = idx;
            stack.pop_back();
        }
        stack.push_back(idx);
    }
    return res;
}

int oddEvenJumps(vector<int>& arr) {
    int n = (int) arr.size();
    vector<int> asc(n), desc(n);
    for (int i = 0; i < n; i++) {
        asc[i] = i;
        desc[i] = i;
    }
    sort(asc.begin(), asc.end(), [&](int a, int b) { return arr[a] != arr[b] ? arr[a] < arr[b] : a < b; });
    sort(desc.begin(), desc.end(), [&](int a, int b) { return arr[a] != arr[b] ? arr[a] > arr[b] : a < b; });
    vector<int> nextHigher = oejNext(asc, n);
    vector<int> nextLower = oejNext(desc, n);
    vector<bool> odd(n, false), even(n, false);
    odd[n - 1] = true;
    even[n - 1] = true;
    int count = 1;
    for (int i = n - 2; i >= 0; i--) {
        if (nextHigher[i] >= 0) odd[i] = even[nextHigher[i]];
        if (nextLower[i] >= 0) even[i] = odd[nextLower[i]];
        if (odd[i]) count++;
    }
    return count;
}

JavaScript

var oddEvenJumps = function(arr) {
    var n = arr.length, i;
    var makeNext = function(order) {
        var res = [];
        for (var t = 0; t < n; t++) res.push(-1);
        var stack = [];
        for (t = 0; t < order.length; t++) {
            var idx = order[t];
            while (stack.length > 0 && idx > stack[stack.length - 1]) res[stack.pop()] = idx;
            stack.push(idx);
        }
        return res;
    };
    var base = [];
    for (i = 0; i < n; i++) base.push(i);
    var asc = base.slice();
    asc.sort(function(a, b) { return arr[a] !== arr[b] ? arr[a] - arr[b] : a - b; });
    var desc = base.slice();
    desc.sort(function(a, b) { return arr[a] !== arr[b] ? arr[b] - arr[a] : a - b; });
    var nextHigher = makeNext(asc);
    var nextLower = makeNext(desc);
    var odd = [], even = [];
    for (i = 0; i < n; i++) { odd.push(false); even.push(false); }
    odd[n - 1] = true;
    even[n - 1] = true;
    var count = 1;
    for (i = n - 2; i >= 0; i--) {
        if (nextHigher[i] >= 0) odd[i] = even[nextHigher[i]];
        if (nextLower[i] >= 0) even[i] = odd[nextLower[i]];
        if (odd[i]) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming