Odd Even Jump LeetCode solution in Python

1
class Solution:
2
    def oddEvenJumps(self, arr: List[int]) -> int:
3

4
        l = len(arr)
5
        res = [False] * l
6
        res[-1] = True
7

8
        # for odd jump: for i, get next larger one
9
        odd_next = [i for i in range(l)]
10
        stack = []  # mono inc for ind
11
        for n, i in sorted([(arr[i], i) for i in range(l)]):
12
            while stack and stack[-1] < i:
13
                odd_next[stack.pop()] = i
14
            stack.append(i)
15

16
        # for even jump: for i, get next smaller one
17
        even_next = [i for i in range(l)]
18
        stack = []  # mono inc for ind
19
        for n, i in sorted([(-arr[i], i) for i in range(l)]):
20
            while stack and stack[-1] < i:
21
                even_next[stack.pop()] = i
22
            stack.append(i)
23

24
        # dp
25
        @lru_cache(None)
26
        def dp(i, odd):
27
            if i == l - 1:
28
                return True
29
            ind = odd_next[i] if odd else even_next[i]
30

31
            if ind == i:
32
                return False
33

34
            return dp(ind, not odd)
35

36
        for i in range(l - 1):
37
            res[i] = dp(i, True)
38
        return sum(res)