Jump Game
Picture
At position 0 with value 2, we can reach positions 1 or 2. We do not need to choose the exact landing yet.
Predict
Must greedy choose one exact jump path?
Walk through the small example
No. All exact paths collapse into one invariant: the farthest end of the reachable prefix.
Mental model and complete Python solution
Do not ask “where should I jump?” Ask “how far can any jump from the known reachable region get?” One boundary represents all paths explored implicitly.
What the function promises: Return whether the final position is reachable. Values are nonnegative integers; an empty list returns False.
def can_reach_end(values):
if not values: return False
farthest = 0
for index, jump in enumerate(values):
if index > farthest: return False
farthest = max(farthest, index+jump)
if farthest >= len(values)-1: return True
return True
assert can_reach_end([2,3,1,1,4])
assert not can_reach_end([3,2,1,0,4])Work and storage: O(n) time and O(1) space.
When to recognize it: All exact paths collapse into one invariant: the farthest end of the reachable prefix.
Check before applying it: This does not directly minimize jump count, and backward or negative moves change the structure.
Change one rule
Return the minimum number of jumps.
See what changes
Treat each current reachable interval as one BFS layer and extend the next interval’s farthest boundary.
Connect
greedy proof: The frontier summarizes every path without committing to one.
bfs: Minimum jumps can be viewed as expanding reach in layers.