leetcode/0055-jump-game.py at master · rustykitty/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
"""
55. Jump Game

Submitted: March 8, 2026

Runtime: 4498 ms (beats 6.03%)
Memory: 69.08 MB (beats 5.05%)
"""

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if all(x != 0 for x in nums):
            return True

        # last occurrence of zero
        last_zero = -1
        for i in range(len(nums)):
            if nums[i] == 0:
                last_zero = i
        self.last_zero = last_zero

        self.nums = nums
        return self._canJump(0)

    @functools.cache
    def _canJump(self, i = 0):
        nums = self.nums

        n = len(nums)
        if i == n - 1:
            return True

        length = nums[i]
        if length == 0:
            return False

        if i > self.last_zero:
            return True

        return any(
            # iterate [1, 2, 3, ..., length] in reverse order
            self._canJump(j) for j in range(min(i + length, n - 1), i, -1)
        )