We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Odd Even Jump

Number: 1017

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an integer array arr, you can jump from a starting index by performing a series of jumps. On odd-numbered jumps, you jump to the index j (with i < j) such that arr[i] <= arr[j] and arr[j] is the smallest possible value reachable; if multiple candidates exist, pick the smallest index. On even-numbered jumps, you jump to the index j (with i < j) such that arr[i] >= arr[j] and arr[j] is the largest possible value reachable; if multiple candidates exist, pick the smallest index. An index is "good" if starting from it you can eventually reach the last index. Return the number of good starting indices.

Key Insights

  • Use dynamic programming to determine if you can reach the end from each index for odd and even jumps.
  • Precompute the next jump index for odd and even jumps using a monotonic stack technique.
  • Sort indices by value (and index to break ties) for odd jumps and sort by descending order for even jumps.
  • Use two DP arrays: one represents if we can reach the end starting with an odd jump, another for even jumps.
  • The answer is the count of indices where starting with an odd jump (the first jump) leads to the end.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the indices. Space Complexity: O(n) for the DP arrays and precomputed jump arrays.

Solution

We start by precomputing the next jump destination for both odd and even jumps using a monotonic stack approach. For odd jumps, sort the indices in increasing order based on arr values (and index in case of a tie) then use a stack to compute the nearest higher or equal index. For even jumps, do a similar procedure but sort indices in decreasing order to compute the next lower or equal index.

Once we have these jump targets, we fill two DP arrays: dpOdd and dpEven. dpOdd[i] indicates that starting from index i with an odd jump can reach the end, while dpEven[i] serves the even jump case. We know the last index is always reachable, giving dpOdd[n - 1] = dpEven[n - 1] = true. We then iterate backwards from the penultimate index to the start, setting:

  • dpOdd[i] = dpEven[nextHigher[i]] if a valid next index exists.
  • dpEven[i] = dpOdd[nextLower[i]] if a valid next index exists. Finally, the answer is the count of indices i for which dpOdd[i] is true since the first jump is odd.

Code Solutions

# Python Solution

class Solution:
    def oddEvenJumps(self, arr):
        n = len(arr)
        # DP arrays to hold if index i can reach the end starting with odd or even jump
        dp_odd = [False] * n
        dp_even = [False] * n
        dp_odd[-1] = dp_even[-1] = True  # The last index can always reach the end
        
        # next index for odd jumps (next higher or equal)
        odd_next = [None] * n
        # next index for even jumps (next lower or equal)
        even_next = [None] * n
        
        # Create mapping using monotonic stack for odd jumps using sorted indices (by value then index)
        sorted_idx = sorted(range(n), key=lambda i: (arr[i], i))
        stack = []
        for i in sorted_idx:
            while stack and i > stack[-1]:
                odd_next[stack.pop()] = i
            stack.append(i)
        
        # Create mapping for even jumps using descending order sorted by value then index
        sorted_idx = sorted(range(n), key=lambda i: (-arr[i], i))
        stack = []
        for i in sorted_idx:
            while stack and i > stack[-1]:
                even_next[stack.pop()] = i
            stack.append(i)
        
        # Build dp states from right to left
        for i in range(n - 2, -1, -1):
            if odd_next[i] is not None:
                dp_odd[i] = dp_even[odd_next[i]]
            if even_next[i] is not None:
                dp_even[i] = dp_odd[even_next[i]]
        
        # Count indices where starting with odd jump can reach the end
        return sum(dp_odd)

# Example usage:
# sol = Solution()
# print(sol.oddEvenJumps([10,13,12,14,15]))  # Output: 2
← Back to All Questions