#975

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Odd Even Jump

Determine the number of valid starting indices in an array where you can reach the end with alternating odd and even jumps.

array dynamic programming stack sorting monotonic stack

Problem Statement

You are given an array arr where you can jump between indices, alternating between odd and even-numbered jumps. Odd-numbered jumps (1st, 3rd, etc.) move you to the smallest index greater than or equal to the current one, while even-numbered jumps (2nd, 4th, etc.) move you to the largest index less than or equal to the current one. A starting index is considered good if you can reach the last index using these alternating jumps.

Your task is to find how many starting indices in the array allow you to reach the last index through these jumps. Note that not all starting indices will be valid; you need to check for each index whether a valid sequence of jumps exists that leads to the end.

Examples

Example 1

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

Output: 2

From starting index i = 0, we can make our 1st jump to i = 2 (since arr[2] is the smallest among arr[1], arr[2], arr[3], arr[4] that is greater or equal to arr[0]), then we cannot jump any more. From starting index i = 1 and i = 2, we can make our 1st jump to i = 3, then we cannot jump any more. From starting index i = 3, we can make our 1st jump to i = 4, so we have reached the end. From starting index i = 4, we have reached the end already. In total, there are 2 different starting indices i = 3 and i = 4, where we can reach the end with some number of jumps.

Example 2

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

Output: 3

From starting index i = 0, we make jumps to i = 1, i = 2, i = 3: During our 1st jump (odd-numbered), we first jump to i = 1 because arr[1] is the smallest value in [arr[1], arr[2], arr[3], arr[4]] that is greater than or equal to arr[0]. During our 2nd jump (even-numbered), we jump from i = 1 to i = 2 because arr[2] is the largest value in [arr[2], arr[3], arr[4]] that is less than or equal to arr[1]. arr[3] is also the largest value, but 2 is a smaller index, so we can only jump to i = 2 and not i = 3 During our 3rd jump (odd-numbered), we jump from i = 2 to i = 3 because arr[3] is the smallest value in [arr[3], arr[4]] that is greater than or equal to arr[2]. We can't jump from i = 3 to i = 4, so the starting index i = 0 is not good. In a similar manner, we can deduce that: From starting index i = 1, we jump to i = 4, so we reach the end. From starting index i = 2, we jump to i = 3, and then we can't jump anymore. From starting index i = 3, we jump to i = 4, so we reach the end. From starting index i = 4, we are already at the end. In total, there are 3 different starting indices i = 1, i = 3, and i = 4, where we can reach the end with some number of jumps.

Example 3

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

Output: 3

We can reach the end from starting indices 1, 2, and 4.

Constraints

1 <= arr.length <= 2 * 104
0 <= arr[i] < 105

Solution Approach

Dynamic Programming with Monotonic Stacks

Use dynamic programming (DP) to track whether each index can reach the end through odd and even jumps. Use two separate monotonic stacks to handle odd and even jump conditions efficiently. By maintaining the stacks in a way that always points to the next valid jump, you can determine if a valid path exists from each index.

Efficient Transition Handling

For each index, consider both odd and even jump possibilities by transitioning between valid indices. A monotonic stack for odd-numbered jumps helps find the next index that satisfies the condition for odd jumps, and similarly for even-numbered jumps. This reduces the number of comparisons needed for each index.

Space and Time Complexity Optimization

Optimize the space complexity by only storing the DP results for relevant indices and reducing redundant calculations with the help of the stacks. The time complexity primarily depends on the number of jumps needed for each index, with a significant optimization from the use of stacks.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(n log n) due to the sorting and stack operations for each jump condition. The space complexity is O(n), as we store DP results and the stacks for both odd and even jump conditions.

What Interviewers Usually Probe

Understanding dynamic programming with alternating conditions is crucial for solving this problem efficiently.
Candidate should demonstrate the ability to optimize time complexity, especially with the use of monotonic stacks.
The ability to explain the transitions between states and why monotonic stacks help is key to a strong solution.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the conditions for odd and even jumps, leading to incorrect transitions between states.
Using brute-force solutions without utilizing sorting and stacks, which could lead to time-limit exceeded errors.
Failing to consider edge cases like already being at the end of the array or having no valid path.

Follow-up variants

Consider modifying the problem to find the minimum number of jumps to reach the end instead of counting valid starting indices.
Extend the problem to support arrays with negative numbers or varying jump conditions.
Instead of alternating odd and even jumps, alternate between forward and backward jumps to test different dynamic programming approaches.

FAQ

What is the pattern used in the Odd Even Jump problem?

The Odd Even Jump problem is a state transition dynamic programming problem that uses alternating odd and even jumps to traverse an array.

How do monotonic stacks help in solving the Odd Even Jump problem?

Monotonic stacks help by efficiently finding the next valid jump index for both odd and even numbered jumps, reducing the time complexity.

What is the time complexity of solving the Odd Even Jump problem?

The time complexity is O(n log n) due to sorting and the stack operations needed to find valid jumps for each index.

Can this problem be solved using brute force?

A brute-force solution is possible but inefficient, as it would likely exceed time limits due to the large number of comparisons required.

What are the edge cases to consider in the Odd Even Jump problem?

Edge cases include arrays with only one element, arrays where no valid starting index exists, or arrays where you are already at the last index.

terminal

Solution

Solution 1: Ordered Set + Memoization Search

We first use an ordered set to preprocess the positions that can be jumped to from each position, recorded in array $g$, where $g[i][1]$ and $g[i][0]$ represent the positions that can be jumped to when the current position is an odd jump or an even jump, respectively. If no position can be jumped to, then both $g[i][1]$ and $g[i][0]$ are $-1$.

class Solution:
    def oddEvenJumps(self, arr: List[int]) -> int:
        @cache
        def dfs(i: int, k: int) -> bool:
            if i == n - 1:
                return True
            if g[i][k] == -1:
                return False
            return dfs(g[i][k], k ^ 1)

        n = len(arr)
        g = [[0] * 2 for _ in range(n)]
        sd = SortedDict()
        for i in range(n - 1, -1, -1):
            j = sd.bisect_left(arr[i])
            g[i][1] = sd.values()[j] if j < len(sd) else -1
            j = sd.bisect_right(arr[i]) - 1
            g[i][0] = sd.values()[j] if j >= 0 else -1
            sd[arr[i]] = i
        return sum(dfs(i, 1) for i in range(n))

Continue Practicing

#907 sum of subarray minimums #853 car fleet #1130 minimum cost tree from leaf values