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)
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