Jump Game II takes the classic "can you reach the end" puzzle one step further: not just whether you can finish, but in the fewest jumps. The clean solution is a greedy sweep that secretly runs a breadth-first search over the array.
Problem. Given an array nums where nums[i] is the maximum jump length from index i, return the
minimum number of jumps to reach the last index. You can always reach the last index.
Example: nums = [2, 3, 1, 1, 4] → answer 2 (jump from index 0 to index 1, then from index 1 to the last index).
The slow way first
The brute-force idea is dynamic programming: min_jumps[i] is the fewest jumps to reach index i, computed by checking every earlier index that can reach i. That works but is O(n²) — for each index you scan a range behind it.
The question to ask: do I really need the exact jump count for every index? No. I only care about the boundary of how far the current number of jumps can take me. That insight collapses the whole thing to one pass.
The idea: BFS by levels
Think of it as breadth-first search. With 0 jumps you can only stand on index 0. With 1 jump you can land anywhere index 0 can reach. With 2 jumps you can reach anywhere those positions can reach — and so on. Each "level" is a contiguous window of indices.
As we scan left to right we track farthest — the best index reachable from anything in the current level. The moment i hits end (the edge of the current level), we have explored that whole level, so we spend a jump and push the boundary out to farthest.
The key insight: we never decide which exact index to jump to. We only track the window each jump opens, and a new jump is counted exactly when the previous window runs out.
Walk through it
Step through the animation. The pointer i scans, the end marker shows the current jump boundary, and farthest tracks the best reach. For nums = [2, 3, 1, 1, 4]: at i = 0 we reach 2, and since i is at the boundary we take jump 1 (window becomes [1..2]). At i = 1 we extend farthest to 4. At i = 2 we hit the boundary again, so jump 2 opens a window covering the last index. Answer: 2.
Pseudocode
jumps = 0
end = 0 # right edge of the current jump window
farthest = 0 # best index reachable from this window
for i from 0 to last index - 1:
farthest = max(farthest, i + nums[i]) # how far this index can throw us
if i == end: # we have walked the whole window
jumps = jumps + 1 # spend a jump
end = farthest # open the next window
return jumpsThe Python solution
def jump(nums):
jumps = 0
end = 0
farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == end:
jumps += 1
end = farthest
return jumpsendis the right edge of the window reachable with the currentjumpscount.farthestis the best index any position in the current window can reach.- We loop only to
len(nums) - 1: once we are about to step onto the last index, the final boundary bump has already been counted. - Line 6 extends the reach; lines 7-9 close the level and start the next one.
- When
i == end, the current window is fully explored, so we must take one more jump and the boundary jumps out tofarthest.
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force (DP) | O(n²) (slow) | scan a range behind each index |
| Greedy BFS (this solution) | O(n) (moderate) | one pass, O(1) work per index |
O(1) (fast)We keep only three integers (jumps, end, farthest), so the extra space is O(1) — a strict improvement over the DP table.
When this pattern shows up
Whenever a problem is about reaching a goal in the fewest steps over a window that only grows, think
greedy boundary sweep. Tracking a single farthest reach instead of every intermediate state turns
an O(n²) search into an O(n) pass — the same move powers interval covering and "minimum taps to water a garden."
Loop to len(nums) - 1, not the full length. If you let i reach the last index, i == end can fire one
extra time and over-count the jumps by one.
Practice
For nums = [2, 3, 1, 1, 4], when i reaches index 2 (the boundary of jump 1), what is farthest and what does the new boundary become?
1. What does farthest represent during the scan?
2. When do we increment the jump count?
3. Why does the loop stop at len(nums) - 1?
4. What is the extra space used by the greedy solution?