Jump Game LeetCode solution in Python

1
# Runtime: 1132 ms (Top 16.52%) | Memory: 15.2 MB (Top 81.46%)
2
class Solution:
3
    def canJump(self, nums: List[int]) -> bool:
4
        """
5
        # Memoization + DFS Solution
6
        # TLE as we have as much as n decisions depending on nums[i] which could be
7
        # 10^5 as an uppercase according to problem constraints
8
        # better off with a greedy approach
9

10
        cache = {} # i : bool
11

12
        def dfs(i):
13
            if i == len(nums) -1:
14
                return True
15
            if nums[i] == 0:
16
                return False
17
            if i in cache:
18
                return cache[i]
19
            for j in range(1, nums[i] + 1):
20
                res = dfs(i + j)
21
                if res:
22
                    cache[i] = True
23
                    return cache[i]
24
            cache[i] = False
25
            return cache[i]
26

27
        return dfs(0)
28
        """
29
        # Greedy Solution
30
        # Key with greedy is to find a local and gobal optimum
31
        # here we find the furthest distance we can travel with each index
32

33
        # futhest index reachable
34
        reachable = 0
35

36
        # iterate through all indexes and if the current index is futher than what we can travel return fasle
37
        for i in range(len(nums)):
38
            if i > reachable:
39
                return False
40

41
            reachable = max(reachable, nums[i] + i)
42
            # if the futherest distance we can jump to is greater or equal than the last index break
43
            if reachable >= len(nums) - 1:
44
                break
45

46
        return True