Odd Even Jump: Monotonic Stack Meets Dynamic Programming

LeetCode 975, Odd Even Jump, is a hard problem that combines two powerful techniques: monotonic stacks and dynamic programming. You are given an array of integers and need to count how many starting indices can reach the last index by following a specific sequence of alternating "odd" and "even" jumps. The trick is that odd jumps and even jumps have opposite rules for choosing where to land, and computing those targets efficiently is the real challenge.

The problem

You are given an array arr of integers. From any index i, you make jumps to reach the end of the array (the last index). Jumps alternate between odd-numbered and even-numbered:

• Odd jump (1st, 3rd, 5th, ...): jump to the index j > i such that arr[j] is the smallest value >= arr[i] among all indices to the right. If there is a tie, pick the smallest j.
• Even jump (2nd, 4th, 6th, ...): jump to the index j > i such that arr[j] is the largest value <= arr[i] among all indices to the right. If there is a tie, pick the smallest j.

You always start with an odd jump (jump #1). An index is "good" if you can reach the last index by following the alternating jump rules. Return the count of good indices.

Input:  arr = [2, 3, 1, 1, 4]
Output: 3

Indices 1, 3, and 4 are good. Index 4 is the last index (trivially good). From index 3, the odd jump lands on index 4 (value 4, the smallest >= 1). From index 1, the odd jump lands on index 4 (value 4, the smallest >= 3). Index 0 and index 2 cannot reach the end.

Two subproblems, one answer

The problem breaks into two parts. First, for every index, figure out where an odd jump and an even jump would land. Second, use DP to determine which indices can actually reach the end.

The naive way to find jump targets is to scan all elements to the right of each index, which takes O(n^2). The key insight is that a monotonic stack can compute all jump targets in O(n log n) time.

Here is the idea. To find odd jump targets (smallest value >= current), sort the indices by (arr[i], i) in ascending order. Then scan through this sorted order and use a monotonic stack to match each index with the next larger index in the original array. The same technique with a reversed sort (descending by value, ascending by index for ties) gives you even jump targets.

Once you have the jump targets, the DP is simple. Define two boolean arrays:

• odd[i]: can you reach the end starting from index i with an odd jump?
• even[i]: can you reach the end starting from index i with an even jump?

The recurrence is: odd[i] = even[oddTarget[i]] and even[i] = odd[evenTarget[i]]. Process from right to left, and the answer is the count of indices where odd[i] is true.

Step-by-step walkthrough

Let's trace through arr = [2, 3, 1, 1, 4] from right to left. At each step, we fill in odd[i] and even[i] using the precomputed jump targets.

Notice how the recurrence chains together. At index 2, the odd jump goes to index 3, but even[3] is false, so odd[2] is false. Meanwhile even[2] looks at odd[3], which is true, so even[2] is true. The alternation between odd and even arrays is what makes this problem tricky to reason about by hand.

The code

def odd_even_jumps(arr):
    n = len(arr)
    if n == 1:
        return 1

    odd_next = [0] * n
    even_next = [0] * n

    def build_next(sorted_indices):
        result = [0] * n
        stack = []
        for i in sorted_indices:
            while stack and stack[-1] < i:
                result[stack.pop()] = i
            stack.append(i)
        return result

    sorted_asc = sorted(range(n), key=lambda i: (arr[i], i))
    odd_next = build_next(sorted_asc)

    sorted_desc = sorted(range(n), key=lambda i: (-arr[i], i))
    even_next = build_next(sorted_desc)

    odd = [False] * n
    even = [False] * n
    odd[-1] = even[-1] = True

    for i in range(n - 2, -1, -1):
        if odd_next[i]:
            odd[i] = even[odd_next[i]]
        if even_next[i]:
            even[i] = odd[even_next[i]]

    return sum(odd)

The build_next function is the core. It takes a list of indices sorted by value and uses a monotonic stack to find, for each index, the next index in sorted order that appears later in the original array. When you sort ascending by (arr[i], i), this finds the odd jump target. When you sort descending by (-arr[i], i), this finds the even jump target.

The DP loop at the bottom fills in the odd and even arrays from right to left. The answer is sum(odd), counting how many indices can reach the end when starting with an odd jump.

Complexity analysis

The sorting step takes O(n log n). Building the next arrays with the monotonic stack takes O(n) each. The DP pass is O(n). Total: O(n log n). Space is O(n) for the arrays.

The brute force approach tries to simulate each path from each index, scanning right to find the jump target each time. That is O(n) per index in the worst case, giving O(n^2) overall.

The building blocks

Monotonic stack for next-element queries

The build_next function is a direct application of the classic "next greater element" monotonic stack pattern. You iterate through elements and maintain a stack of indices that have not yet found their match. When a new element comes in, you pop everything from the stack that it "resolves." The twist here is that instead of iterating through the array in order, you iterate through indices sorted by value. This transforms "find the smallest value >= current to the right" into "find the next index in sorted order that appears later in the array."

Right-to-left DP with boolean states

The DP structure is clean: two boolean arrays, one for odd jumps and one for even jumps, filled from right to left. The recurrence odd[i] = even[target] captures the alternation between jump types. This pattern of maintaining parallel state arrays and cross-referencing them appears in other problems where decisions alternate between two modes.

Edge cases

Before submitting, verify your solution handles:

• Single element [5]: the answer is 1. The last index is always good.
• All identical values like [7, 7, 7, 7]: every odd jump goes to the next index (smallest >= is the same value at the nearest right index). Every even jump also goes to the next index. All indices are good, so the answer equals the length.
• Strictly increasing like [1, 2, 3, 4]: odd jumps always go to the next index. Even jumps have no valid target (no smaller or equal value to the right except for ties). Only the last index is guaranteed good, plus any index whose odd jump chain reaches the end.
• Strictly decreasing like [4, 3, 2, 1]: odd jumps have no target from any index except the last (no value >= current to the right). Even jumps go to the next index. Only the last index is good, so the answer is 1.
• Two elements [1, 2]: odd jump from index 0 goes to index 1 (2 >= 1). That reaches the end. Answer: 2.

From understanding to recall

You have seen how to combine a monotonic stack with DP to solve Odd Even Jump. The monotonic stack computes jump targets in O(n log n) by processing sorted indices. The DP fills two boolean arrays from right to left, cross-referencing odd and even states.

The challenge with this problem is remembering the setup. How do you sort indices to find odd jump targets vs. even jump targets? Which direction does the DP go? What is the recurrence? These details are easy to mix up under pressure. Spaced repetition lets you practice the full solution from scratch at increasing intervals, so the monotonic stack sort trick and the two-array DP become second nature.

Related posts

• Daily Temperatures - Classic monotonic stack problem for finding next greater elements
• Online Stock Span - Another monotonic stack application with backward lookups
• Jump Game - Simpler reachability problem on arrays