LeetCode 975: Odd Even Jump

Problem Restatement

We are given an integer array arr.

From any starting index, we make jumps to the right. The jumps are numbered by jump count:

For an odd jump from index i, we must jump to an index j such that:

i < j
arr[i] <= arr[j]

Among all possible j, choose the one with the smallest possible arr[j]. If there is a tie, choose the smallest index j.

For an even jump from index i, we must jump to an index j such that:

i < j
arr[i] >= arr[j]

Among all possible j, choose the one with the largest possible arr[j]. If there is a tie, choose the smallest index j.

A starting index is good if we can reach the last index by following these rules.

Return the number of good starting indices.

The official constraints are 1 <= arr.length <= 2 * 10^4 and 0 <= arr[i] < 10^5.

Input and Output

Example function shape:

def oddEvenJumps(arr: list[int]) -> int:
    ...

Examples

Example 1:

arr = [10, 13, 12, 14, 15]

Output:

2

The good starting indices are 3 and 4.

From index 3, the first odd jump goes to index 4.

Index 4 is already the last index, so it is good.

Example 2:

arr = [2, 3, 1, 1, 4]

Output:

3

The good starting indices are 1, 3, and 4.

Example 3:

arr = [5, 1, 3, 4, 2]

Output:

3

The good starting indices are 1, 2, and 4.

First Thought: Simulate From Every Index

A direct idea is to start from every index and simulate jumps.

For each jump, we search all later indices to find the required destination.

For odd jumps, search for the smallest value greater than or equal to arr[i].

For even jumps, search for the largest value less than or equal to arr[i].

This can be too slow.

There are n possible starts, and each jump search may scan O(n) elements. We need to precompute jump destinations efficiently.

Key Insight

Separate the problem into two parts.

First, compute:

next_odd[i]

the index reached by an odd jump from i.

Also compute:

next_even[i]

the index reached by an even jump from i.

Then use dynamic programming:

odd[i] = can reach the end from i when the next jump is odd
even[i] = can reach the end from i when the next jump is even

The last index is always good:

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

Then:

odd[i] = even[next_odd[i]]
even[i] = odd[next_even[i]]

if those next jumps exist.

Computing Next Odd Jumps

For odd jumps, we need the smallest value to the right that is greater than or equal to arr[i].

If multiple indices have that same value, choose the smallest index.

We can compute this with sorting and a monotonic stack.

Sort indices by:

(arr[i], i)

This puts smaller values first. For equal values, smaller indices come first.

Then use a stack to assign next greater-or-equal destinations.

When we scan sorted indices, if the current index is greater than the stack top, then the current index is the correct next odd jump for that stack-top index.

Computing Next Even Jumps

For even jumps, we need the largest value to the right that is less than or equal to arr[i].

Sort indices by:

(-arr[i], i)

This puts larger values first. For equal values, smaller indices come first.

Then use the same monotonic stack process.

This assigns next lower-or-equal destinations.

Helper Idea

The same helper can compute next jumps from an ordering of indices.

def make_next(indices):
    stack = []
    result = [-1] * n

    for index in indices:
        while stack and index > stack[-1]:
            result[stack.pop()] = index
        stack.append(index)

    return result

Why this works:

The sorted order guarantees value priority.

The stack logic guarantees the destination is to the right and has the smallest possible index among valid destinations.

Algorithm

1. Let n = len(arr).
2. Build next_odd:
   • Sort indices by (arr[i], i).
   • Run the monotonic stack helper.
3. Build next_even:
   • Sort indices by (-arr[i], i).
   • Run the same helper.
4. Create arrays:

odd = [False] * n
even = [False] * n

5. Set:

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

6. Process indices from right to left:
   • If next_odd[i] != -1, set odd[i] = even[next_odd[i]].
   • If next_even[i] != -1, set even[i] = odd[next_even[i]].
7. Return the number of True values in odd.

We count odd because the first jump from a starting index is jump number 1, which is odd.

Correctness

The sorted-index helper computes the correct odd and even jump destinations.

For odd jumps, sorting by (arr[i], i) considers candidate destinations in increasing value order, and for equal values in increasing index order. Therefore, the first valid right-side candidate assigned to an index is exactly the required smallest value greater than or equal to arr[i], with the smallest index tie-break.

For even jumps, sorting by (-arr[i], i) considers candidate destinations in decreasing value order, and for equal values in increasing index order. Therefore, the first valid right-side candidate assigned to an index is exactly the required largest value less than or equal to arr[i], with the smallest index tie-break.

After jump destinations are known, the dynamic programming recurrence is direct. If the next jump from index i is odd, we must go to next_odd[i], and after that the next jump is even. So odd[i] is true exactly when even[next_odd[i]] is true. The even case is symmetric.

The last index is reachable from itself with no further jumps, so both odd[n - 1] and even[n - 1] are true.

Since the DP processes indices from right to left and every jump goes to a larger index, all needed future states are already computed. Therefore, odd[i] correctly tells whether starting at i can reach the end. Counting true values in odd gives exactly the number of good starting indices.

Complexity

Let n = len(arr).

Implementation

class Solution:
    def oddEvenJumps(self, arr: list[int]) -> int:
        n = len(arr)

        def make_next(indices: list[int]) -> list[int]:
            result = [-1] * n
            stack = []

            for index in indices:
                while stack and index > stack[-1]:
                    result[stack.pop()] = index

                stack.append(index)

            return result

        odd_order = sorted(range(n), key=lambda i: (arr[i], i))
        even_order = sorted(range(n), key=lambda i: (-arr[i], i))

        next_odd = make_next(odd_order)
        next_even = make_next(even_order)

        odd = [False] * n
        even = [False] * n

        odd[-1] = True
        even[-1] = True

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

            if next_even[i] != -1:
                even[i] = odd[next_even[i]]

        return sum(odd)

Code Explanation

The helper builds next-jump destinations:

def make_next(indices: list[int]) -> list[int]:

It receives indices in the correct value order.

The stack stores indices whose jump target has not been found yet:

stack = []

When the current index is to the right of the stack top:

while stack and index > stack[-1]:
    result[stack.pop()] = index

the current index becomes that previous index’s jump destination.

For odd jumps:

odd_order = sorted(range(n), key=lambda i: (arr[i], i))

This handles smallest greater-or-equal value and smallest index tie-break.

For even jumps:

even_order = sorted(range(n), key=lambda i: (-arr[i], i))

This handles largest smaller-or-equal value and smallest index tie-break.

The DP arrays mean:

odd[i]
even[i]

whether we can reach the end from index i when the next jump is odd or even.

The last index is always reachable:

odd[-1] = True
even[-1] = True

Then we fill states from right to left:

for i in range(n - 2, -1, -1):

If an odd jump exists:

odd[i] = even[next_odd[i]]

If an even jump exists:

even[i] = odd[next_even[i]]

Finally:

return sum(odd)

counts good starting indices.

Testing

def run_tests():
    s = Solution()

    assert s.oddEvenJumps([10, 13, 12, 14, 15]) == 2
    assert s.oddEvenJumps([2, 3, 1, 1, 4]) == 3
    assert s.oddEvenJumps([5, 1, 3, 4, 2]) == 3

    assert s.oddEvenJumps([1]) == 1
    assert s.oddEvenJumps([1, 2, 3, 4]) == 2
    assert s.oddEvenJumps([4, 3, 2, 1]) == 1
    assert s.oddEvenJumps([2, 2, 2]) == 3
    assert s.oddEvenJumps([1, 3, 2, 4, 5]) == 4

    print("all tests passed")

run_tests()

Test meaning: