Odd Even Jump — Hard Problem & Solution

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…

Difficulty: Hard
Topics: Arrays, Dynamic Programming, Stack, Monotonic Stack, Ordered Set
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

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

Sort the indices by (value, index) ascending; a monotonic stack over that order yields nextHigher.
Sort by (value descending, index ascending); the same stack pass yields nextLower.
Set odd[n-1] = even[n-1] = true.
For i from n-2 down: odd[i] = even[nextHigher[i]] and even[i] = odd[nextLower[i]] where the targets exist.
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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue