Jump Game II
Find the fewest jumps to the last index in one greedy pass: each jump covers a window, and the next window ends at the farthest reach.
Problem Understanding
Jump Game II: nums[i] is the longest jump you can make from index i. Starting at index 0, return the fewest jumps to reach the last index. The last index is always reachable.
Example: [2, 3, 1, 1, 4] returns 2: jump from 0 to 1, then from 1 to 4.
Attempt 1: DP Over Every Jump
Let dp[j] be the fewest jumps to reach j, and for every i relax every j in i + 1 .. i + nums[i]. It is correct but O(n²) in the worst case, because the same indices are relaxed from many starting points. In Jump Game one number replaced a whole set of reachable indices; the same idea works here.
The Intuition: Jumps Are BFS Levels
With 0 jumps you can only be on index 0. With 1 jump you can be anywhere in 1 .. nums[0]. In general, the indices first reachable with k jumps form one contiguous window, and the next window ends at the farthest index any index in this window can reach.
So walk the array once with two numbers:
farthest: the besti + nums[i]seen so far.end: the right edge of the current window.
When i reaches end, the current window is used up: count one more jump and set end = farthest. That is a greedy BFS with no queue.
Interactive Walkthrough
The second row labels each index with the jump whose window first covers it. Watch farthest grow while the scan crosses a window, and a new window appear each time the scan reaches end.
Dry Run Table
Input: [2, 3, 1, 1, 4]
| i | nums[i] | farthest | i == end? | jumps | end |
|---|---|---|---|---|---|
| 0 | 2 | 2 | yes | 1 | 2 |
| 1 | 3 | 4 | no | 1 | 2 |
| 2 | 1 | 4 | yes | 2 | 4 |
| 3 | 1 | 4 | no | 2 | 4 |
The loop stops before index 4. The answer is 2.
The Solution Template
One pass with a window end and a farthest reach.
Jump Game II Code
1var jump = function(nums) {2 let jumps = 0, end = 0, farthest = 0;3 for (let i = 0; i < nums.length - 1; i++) {4 farthest = Math.max(farthest, i + nums[i]);5 if (i === end) {6 jumps++;7 end = farthest;8 }9 }10 return jumps;11};
Edge Cases & Common Mistakes
- One element: you are already at the end; the loop never runs and the answer is
0. - Looping to the last index: if
imay equallen − 1, a window ending exactly there adds one jump too many. - Jumping as far as possible each time: landing on the farthest index is not always best; choosing the window end from the best reach inside the window is.
- Zeros: a 0 inside a window is harmless as long as another index in the window reaches past it.
Summary
The indices reachable with k jumps form a window. Scan once, growing farthest; when i reaches the window's end, count a jump and set end = farthest. Stop before the last index. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet