LeetCode 975 - Odd Even Jump

LeetCode Problem 975

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Stack, Sorting, Monotonic Stack, Ordered Set

Solution

Problem Understanding

The problem asks us to determine how many starting indices in an array allow reaching the last element by performing a series of jumps defined as either odd-numbered or even-numbered. The distinction between odd and even jumps is crucial: odd-numbered jumps must move to the smallest value greater than or equal to the current element, while even-numbered jumps must move to the largest value smaller than or equal to the current element. If there is a tie in value, the smallest index is chosen. A "good" starting index is one from which a series of jumps can reach the final index of the array.

The input is a single integer array arr of size up to 2 * 10^4, with elements ranging from 0 to 100,000. The output is a single integer representing the number of good starting indices. Constraints indicate that a brute-force approach that explores all possible sequences of jumps would be too slow, as it could require exponential time. Important edge cases include arrays of length 1 (where the only index is trivially good), arrays with all identical elements, strictly increasing or decreasing arrays, and arrays with plateaus that could lead to multiple candidate jump indices.

Approaches

A brute-force approach would attempt to simulate every possible jump sequence from each starting index. For each index, we would repeatedly scan forward to find the next valid jump for odd or even jumps. This approach is correct but extremely slow because for each starting index i, we may scan all remaining indices j > i, resulting in O(n^2) or worse, potentially reaching O(n^3) when including recursive or sequential checks to the end.

The key insight for an optimal solution is that the problem can be decomposed using dynamic programming. We can precompute for each index i the next valid odd jump and even jump using a monotonic stack technique combined with sorting. Once the "next jump" for both odd and even jumps is known, we can propagate reachability from the end backward. This approach avoids redundant scanning and allows the problem to be solved in O(n log n) time due to the sorting and stack operations.

Algorithm Walkthrough

1. First, create two arrays odd_next and even_next of length n, where odd_next[i] is the next index reachable via an odd jump from i, and even_next[i] is the next index reachable via an even jump. Initialize all entries with None to indicate no jump is possible.
2. Sort the array indices by value for odd jumps (ascending order) and by value for even jumps (descending order). Ties in value are broken by the original index, since the smallest index must be chosen.
3. Use a monotonic stack to compute the next jump indices. For odd jumps, iterate over the sorted indices. For each index, while the stack is not empty and the current index is greater than the stack's top, pop from the stack and set the popped index's odd_next to the current index. Repeat similarly for even jumps with descending sorted indices.
4. Initialize two boolean arrays odd_reach and even_reach, where odd_reach[i] is True if starting from index i with an odd jump can eventually reach the end. Set odd_reach[-1] and even_reach[-1] to True since the last index is trivially reachable.
5. Iterate backward from the second-to-last index. For each index i, if odd_next[i] exists, set odd_reach[i] = even_reach[odd_next[i]]. If even_next[i] exists, set even_reach[i] = odd_reach[even_next[i]]. This ensures the alternating jump requirement is respected.
6. Count the number of indices where odd_reach[i] is True, since starting with the first jump as odd is required by the problem statement.

Why it works: The approach works because it precomputes the only valid "next jump" for each index according to the problem's rules. Propagating reachability backward ensures that we correctly account for alternating jump constraints while avoiding redundant scanning.

Python Solution

from typing import List

class Solution:
    def oddEvenJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n == 1:
            return 1

        def make_next(indices):
            result = [None] * n
            stack = []
            for i in indices:
                while stack and i > stack[-1]:
                    prev = stack.pop()
                    result[prev] = i
                stack.append(i)
            return result

        # Precompute next jumps
        odd_next = make_next(sorted(range(n), key=lambda i: (arr[i], i)))
        even_next = make_next(sorted(range(n), key=lambda i: (-arr[i], i)))

        # Initialize reachability arrays
        odd_reach = [False] * n
        even_reach = [False] * n
        odd_reach[-1] = even_reach[-1] = True

        # Backward propagation of reachability
        for i in range(n - 2, -1, -1):
            if odd_next[i] is not None:
                odd_reach[i] = even_reach[odd_next[i]]
            if even_next[i] is not None:
                even_reach[i] = odd_reach[even_next[i]]

        return sum(odd_reach)

Implementation Explanation: The function make_next computes the next reachable index for odd or even jumps using a monotonic stack. Sorting ensures that the stack receives indices in the correct order to satisfy the "smallest/largest value with smallest index" requirement. The odd_reach and even_reach arrays use backward propagation to determine which indices can reach the end while respecting jump alternation. Finally, summing odd_reach yields the number of good starting indices.

Go Solution

package main

func oddEvenJumps(arr []int) int {
    n := len(arr)
    if n == 1 {
        return 1
    }

    makeNext := func(indices []int) []int {
        result := make([]int, n)
        for i := range result {
            result[i] = -1
        }
        stack := []int{}
        for _, i := range indices {
            for len(stack) > 0 && i > stack[len(stack)-1] {
                prev := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                result[prev] = i
            }
            stack = append(stack, i)
        }
        return result
    }

    oddIndices := make([]int, n)
    evenIndices := make([]int, n)
    for i := 0; i < n; i++ {
        oddIndices[i] = i
        evenIndices[i] = i
    }
    // sort for odd jumps ascending
    sort.Slice(oddIndices, func(i, j int) bool {
        if arr[oddIndices[i]] == arr[oddIndices[j]] {
            return oddIndices[i] < oddIndices[j]
        }
        return arr[oddIndices[i]] < arr[oddIndices[j]]
    })
    // sort for even jumps descending
    sort.Slice(evenIndices, func(i, j int) bool {
        if arr[evenIndices[i]] == arr[evenIndices[j]] {
            return evenIndices[i] < evenIndices[j]
        }
        return arr[evenIndices[i]] > arr[evenIndices[j]]
    })

    oddNext := makeNext(oddIndices)
    evenNext := makeNext(evenIndices)

    oddReach := make([]bool, n)
    evenReach := make([]bool, n)
    oddReach[n-1], evenReach[n-1] = true, true

    for i := n - 2; i >= 0; i-- {
        if oddNext[i] != -1 {
            oddReach[i] = evenReach[oddNext[i]]
        }
        if evenNext[i] != -1 {
            evenReach[i] = oddReach[evenNext[i]]
        }
    }

    count := 0
    for _, val := range oddReach {
        if val {
            count++
        }
    }
    return count
}

Go Notes: Go requires initializing slices with default values and uses -1 instead of None. Sorting uses sort.Slice with a comparison function. The logic otherwise mirrors the Python solution.

Worked Examples

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

Step 1: Compute next jumps

Step 2: Propagate reachability backward

| Index | Odd Reach | Even Reach |

|-------|-----------|