Problem statement

https://leetcode.com/problems/odd-even-jump/

Solution

First of all make it clear that we always move from left to right. We can see this problem as directed graph, where we need to figure out from how many positions we can reach the ending position.

First, let us deal with odd-numbered jumps. For each index i we need to find such index j, for which value arr[j] >= arr[i] and value as small as possible. Let us sort our arr by pairs (arr[i], i), then for each element in B1 we need to find the smallest index of element to the right, which is bigger than current index. This problem can be solved, using monotonic stack, see for example Problem 0503 Next Greater Element II.

The same logic can be done for even jumps, let us combine them to data list of tuples.

Final step is to use dp(i, par), where i is index and par is parity: odd or even. For each position we can make step in unique way or we can not do it at all. If we reached the end, we return 1. If we can make a move, we return answer for this move with opposite parity. If we can not do a move, we return 0. In the end we check dp(i, 0) for all i and calculate sum.

Complexity

Time complexity is O(n log n) for sort step, O(n) for monotonic stack steps and O(n) for dp step, so final complexity is O(n log n). Space complexity is O(n).

Code

class Solution:
    def oddEvenJumps(self, arr):
        n = len(arr)

        def nextGreater(A):
            ans, stack = [None] * n, []
            for i in A:
                while stack and i > stack[-1]:
                    ans[stack.pop()] = i
                stack.append(i)
            return ans
        
        A1 = sorted((arr[i], i) for i in range(n))
        oddnext = nextGreater([j for _,j in A1])
        
        A2 = sorted((-arr[i], i) for i in range(n))
        evennext = nextGreater([j for _,j in A2])
        
        data = list(zip(oddnext, evennext))
            
        @lru_cache(None)
        def dp(i, par):
            if i == n - 1: return 1
            return dp(data[i][par], 1 - par) if data[i][par] else 0
       
        return sum(dp(i, 0) for i in range(n))

Remark

There is also solution using SortedList with the same complexity.