Jump Game II Solution

Problem

You're standing at the first position of an array where each value tells you the maximum number of steps you can jump forward from that spot. Return the minimum number of jumps needed to reach the last position. The input always guarantees the last position is reachable.

Input: nums = [2, 3, 1, 1, 4]
Output: 2
Explanation: Jump from index 0 to index 1 (within range 2), then from index 1 to index 4 (within range 3).

Counter-example: nums = [2, 3, 0, 1, 4] also returns 2 — landing on the zero at index 2 is fine as long as you jumped over it or reached it already with enough jumps.

Intuition

At any point, every position we can currently stand on defines a "reach horizon" — the farthest index reachable with one more jump. The greedy insight is that we never need to track which specific position we jump from: the moment we exhaust all positions reachable in k jumps, we increment the jump counter and our new horizon becomes the farthest we could have landed with k+1 jumps.

Approach 1 — Dynamic Programming

For each index, look back at all previous positions that can reach it and take the minimum jump count plus one. This is correct but checks every prior position for every current one.

Create a min_jumps array initialized to infinity, with min_jumps[0] = 0.
For each index i from 1 to n-1, scan every earlier index j.
If j + nums[j] >= i, then j can reach i — update min_jumps[i] if min_jumps[j] + 1 is smaller.
Return min_jumps[n-1].

1def jump(nums: list[int]) -> int:
2    n = len(nums)
3    min_jumps = [float('inf')] * n
4    min_jumps[0] = 0
5
6    for i in range(1, n):
7        for j in range(i):
8            if j + nums[j] >= i:  # j can reach i
9                min_jumps[i] = min(min_jumps[i], min_jumps[j] + 1)
10
11    return min_jumps[-1]

Time: O(n²) — for each of the n positions, we scan all previous positions.
Space: O(n) — the min_jumps array.

Approach 2 — Greedy (Single Pass)

Track current_end (farthest position reachable with the current number of jumps) and farthest (farthest position reachable by jumping once from anywhere in the current range). Each time we reach current_end, we commit to one more jump and extend our boundary.

Initialize jumps = 0, current_end = 0, farthest = 0.
Loop i from 0 to n-2 (stop before the last index — arriving there doesn't cost a jump).
Update farthest = max(farthest, i + nums[i]).
When i == current_end, we've scanned the full current range — increment jumps and advance current_end = farthest.
Return jumps.

1def jump(nums: list[int]) -> int:
2    jumps = 0
3    current_end = 0
4    farthest = 0
5
6    for i in range(len(nums) - 1):  # stop before last; reaching it doesn't need a jump
7        farthest = max(farthest, i + nums[i])
8        if i == current_end:  # exhausted every position reachable with current jumps
9            jumps += 1
10            current_end = farthest
11
12    return jumps

Time: O(n) — a single pass through the array.
Space: O(1) — only three integer variables.

Complexity Summary

Approach	Time	Space	When to use
Dynamic Programming	O(n²)	O(n)	Easier to reason about; fine for small inputs
Greedy	O(n)	O(1)	Always prefer this — constant space, linear time

Common Mistakes

Iterating to n-1 instead of n-2 — the last index is the destination; when i reaches it, we've already jumped there and shouldn't increment the counter again.
Confusing this with Jump Game I — the predecessor only asks "can you reach the end?" and never needs a jump counter; copy-pasting that solution here and adding a counter produces wrong results.
Updating current_end inside the farthest update — current_end must only change at the boundary check (if i == current_end), not every iteration; mixing the two causes the jump count to grow too fast.
Thinking you need to track the specific jump position — you never need to record which index you jumped from; the greedy correctness relies only on knowing the maximum reach, not the source.
Off-by-one on single-element input — when len(nums) == 1, the loop body never runs and the function correctly returns 0.

Jump Game II — Solution