Jump Game
Decide whether the last index is reachable by tracking the furthest position you can get to
Problem Statement
You are given an array nums. You start at index 0, and nums[i] is the maximum jump length from position i. Return true if you can reach the last index.
Input: nums = [2, 3, 1, 1, 4]
Output: true
Why: jump 1 to index 1, then 3 to index 4
Input: nums = [3, 2, 1, 0, 4]
Output: false
Why: every route lands on index 3, whose value is 0 — a dead end'Maximum' is the word that matters
nums[i] = 3 means you may jump 1, 2 or 3 steps — not exactly 3. That flexibility is what makes a greedy solution possible: reaching a position means you can also reach every position before it.
Intuition
The instinct is to explore every choice — a decision tree with up to nums[i] branches per node, which is exponential. Dynamic programming brings that down to O(n²) by caching reachability per index. Both work. Both are more machinery than this problem needs.
The key insight
Forget which jumps you take. Track a single number: the furthest index reachable so far.
Walk left to right. At index i:
- If
i > furthest, you cannot even stand here — everything beyond is unreachable too. Returnfalse. - Otherwise update
furthest = max(furthest, i + nums[i]).
If you get through the array, the last index was reachable.
Why is one number enough? Because reachability is contiguous. If index k is reachable, so is every index below k — you simply jump shorter. So the reachable set is always a prefix [0, furthest], and a prefix is fully described by its right end.
Real-world analogy
Crossing a river on stepping stones where each stone lets you leap up to a certain distance. You do not plan the exact route. You just keep asking: how far can I possibly get from everything I've reached so far? If your reach stops short of the next stone, no route exists.
Watch it run
Approach
Walk i from 0 to n-1
If i > furthest, position i is unreachable → return false immediately.
Extend the reach
furthest = max(furthest, i + nums[i]).
Return true if the loop completes
Reaching the end of the loop means every index, including the last, was reachable.
Solution
def can_jump(nums: list[int]) -> bool:
"""True if the last index is reachable from index 0."""
furthest = 0
for i, jump in enumerate(nums):
if i > furthest:
return False # this index is beyond anything we can reach
furthest = max(furthest, i + jump)
return TrueAn equivalent early-exit form that stops as soon as the goal is covered:
def can_jump_early(nums: list[int]) -> bool:
furthest = 0
last = len(nums) - 1
for i, jump in enumerate(nums):
if i > furthest:
return False
furthest = max(furthest, i + jump)
if furthest >= last:
return True
return TrueThe backwards variant
Equally valid, and some find it more intuitive — shrink the goalpost toward the start:
def can_jump_backwards(nums: list[int]) -> bool:
goal = len(nums) - 1
for i in range(len(nums) - 2, -1, -1):
if i + nums[i] >= goal:
goal = i # i can reach the goal, so i becomes the new goal
return goal == 0Why greedy is provably correct here
The greedy choice is "always extend the reach as far as possible". It is safe because reachability is monotone: if you can reach index k, you can reach every index below it. So a larger furthest is never worse than a smaller one, and there is no scenario where holding back opens a route that reaching further would have closed.
Greedy fails on problems where an early large gain blocks a later, bigger one. That cannot happen here.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
- Time — one pass, constant work per index. The DP alternative is
O(n²); brute-force search is exponential. - Space — one integer.
Edge Cases
Related Problems
- Jump Game II — the same setup, but counting the minimum number of jumps
- Gas Station — another greedy proof about what can safely be skipped
- Best Time to Buy and Sell Stock — one pass, one remembered extreme