LC 0055 [M] Jump Game - ALawliet/algorithms GitHub Wiki

DP is O(n^2) but we can greedy shift the goal towards us for O(n)

https://youtu.be/Yan0cv2cLy8

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

loop through each index while tracking the furthest position we can jump so far from those indexes, bail early if we get to a index that exceeds the furthest position we were previously able to jump to

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        global_max_pos = 0

        for i in range(len(nums)):
            if i > global_max_pos: return False
            local_max_pos = i + nums[i]
            global_max_pos = max(global_max_pos, local_max_pos)

        return True