Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1017. Odd Even Jump

My accepted Python solution to LeetCode problem 1017, Odd Even Jump, running in 111ms.

  • Difficulty: Hard
  • Python
  • Runtime 111ms
  • Memory 22.7MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 111ms, memory 22.7MB, accepted 2026-01-01.

python
class Solution:
    def oddEvenJumps(self, arr: List[int]) -> int:
        n = len(arr)
        
        # For each index, find next index for odd jump (smallest value >= current)
        # and even jump (largest value <= current)
        
        # Using monotonic stack with sorted indices
        def make_next(sorted_indices):
            result = [None] * n
            stack = []
            for i in sorted_indices:
                while stack and stack[-1] < i:
                    result[stack.pop()] = i
                stack.append(i)
            return result
        
        # For odd jumps: sort by value, then by index for ties
        sorted_odd = sorted(range(n), key=lambda i: (arr[i], i))
        next_odd = make_next(sorted_odd)
        
        # For even jumps: sort by -value, then by index for ties
        sorted_even = sorted(range(n), key=lambda i: (-arr[i], i))
        next_even = make_next(sorted_even)
        
        # DP: can_reach_odd[i] = can reach end with odd jump from i
        #     can_reach_even[i] = can reach end with even jump from i
        can_reach_odd = [False] * n
        can_reach_even = [False] * n
        can_reach_odd[-1] = can_reach_even[-1] = True
        
        for i in range(n - 2, -1, -1):
            if next_odd[i] is not None:
                can_reach_odd[i] = can_reach_even[next_odd[i]]
            if next_even[i] is not None:
                can_reach_even[i] = can_reach_odd[next_even[i]]
        
        # Count good starting indices (first jump is odd)
        return sum(can_reach_odd)

Source