LeetCode 55 · Greedy · concept: greedy
Problem
Each nums[i] is the max jump length from index i. Starting at index 0, can you reach the last index?
[2,3,1,1,4] -> true
[3,2,1,0,4] -> false (stuck at index 3)
Approach — track the farthest reachable index (optimal)
Sweep left to right, maintaining the farthest index reachable so far. If you ever stand on an index beyond that reach, you’re stuck. If reach ever covers the last index, success.
def canJump(nums):
farthest = 0
for i in range(len(nums)):
if i > farthest:
return False # can't even get to i
farthest = max(farthest, i + nums[i])
if farthest >= len(nums) - 1:
return True
return TrueTime O(n), space O(1).
Greedy beats DP here
A DP (“is index i reachable?”) is O(n²). The greedy insight: you don’t need to know how you reach an index, only whether the running maximum reach covers it. Extending farthest as you go, and failing the moment i outruns it, captures reachability in one pass. (An equivalent backward greedy shrinks a “goal” post toward 0.)
Key insight
Reachability with variable steps → track a single farthest-reachable frontier. Collapsing “all the ways to get here” into one running maximum is the greedy move that turns O(n²) DP into O(n).
Related
- concept: greedy
- prev: Maximum Subarray · next: Jump Game II
Software engineering
Infrastructure & security
Computer science
Hardware & engineering