55. Jump Game

Solution 1: DP (Tail -> Head)

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        N = len(nums)
        isIdxReachableToEnd = (N-1)*[False] + [True]
        for idx in range(N-2, -1, -1):
            for jumpStep in range(nums[idx]+1):
                if idx + jumpStep > N - 1:
                    break
                if nums[idx + jumpStep]:
                    isIdxReachableToEnd[idx] = True
                    break
        return isIdxReachableToEnd[0]

Time Complexity: O(N*M) // N = len(nums), M = max(nums[i])
Space Complexity: O(N)

Solution 2: Greedy (Tail -> Head)

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        N = len(nums)
        minIdxRecheableToEnd = N - 1
        for idx in range(N - 2, -1, -1):
            if idx + nums[idx] >= minIdxRecheableToEnd:
                minIdxRecheableToEnd = idx
        return minIdxRecheableToEnd == 0

Time Complexity: O(N)
Space Complexity: O(1)

Solution 3: Greedy (Head -> Tail)

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        N = len(nums)
        maxRecheableIdx = 0
        for idx in range(N):
            # Can't even jump to this Idx
            if maxRecheableIdx < idx:
                return False
            
            maxRecheableIdx = max(maxRecheableIdx, idx + nums[idx])
            
            # Can jump to the end from this Idx 
            if maxRecheableIdx >= N - 1:
                return True
                
        return maxRecheableIdx >= N - 1

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/jump-game/discuss/20917/Linear-and-simple-solution-in-C%2B%2B
https://leetcode.com/problems/jump-game/discuss/20900/Simplest-O(N)-solution-with-constant-space