Jump Game II
Find the minimum number of jumps to the end by treating each jump as a BFS level
Problem Statement
You are given an array nums. You start at index 0, and nums[i] is the maximum jump length from position i. The last index is guaranteed reachable.
Return the minimum number of jumps needed to reach the last index.
Input: nums = [2, 3, 1, 1, 4]
Output: 2
Why: index 0 → index 1 (jump of 1), then index 1 → index 4 (jump of 3)
Input: nums = [2, 3, 0, 1, 4]
Output: 2Intuition
Jump Game asked whether the end is reachable. This asks for the cheapest route, which sounds like it needs real search. It does not.
The key insight — think in levels, not in jumps
Group the indices by how many jumps it takes to reach them:
nums = [2, 3, 1, 1, 4]
0 jumps: index 0
1 jump: indices 1–2 (from index 0 you can reach up to 0 + 2 = 2)
2 jumps: indices 3–4 (from 1 you reach 4; from 2 you reach 3 — union is 3–4)Each level is a contiguous range, for the same reason as in Jump Game: reachability is monotone. So instead of tracking individual positions, track the range boundary.
This is breadth-first search where each "level" is one more jump — but because the levels are intervals, you never need an actual queue.
The two boundaries
current_end— the last index reachable with the jumps counted so far. Crossing it means you must spend another jump.furthest— the furthest index reachable using one more jump from anywhere in the current level.
When i reaches current_end, the current level is exhausted: increment the jump count and set current_end = furthest.
Real-world analogy
Flight connections. Level 0 is your home city. Level 1 is everywhere reachable with one flight. Level 2 is everywhere reachable with two. To find the fewest flights to a destination, you expand a whole level at a time rather than tracing individual itineraries.
Watch it run
Approach
Track three numbers
jumps = 0, current_end = 0, furthest = 0.
Loop i from 0 to n - 2
Stopping one short of the end is essential — see the warning below.
Extend the reach
furthest = max(furthest, i + nums[i]).
When i == current_end, spend a jump
Increment jumps and set current_end = furthest. You have consumed the entire current level.
The loop must stop at n - 2
If the loop included the last index and current_end happened to equal n - 1, it would count one extra jump after arriving — an off-by-one that returns 3 instead of 2.
Excluding the final index encodes the fact that arriving is free; only departing costs a jump.
Solution
def jump(nums: list[int]) -> int:
"""Minimum number of jumps to reach the last index."""
jumps = 0
current_end = 0 # last index reachable with `jumps` jumps
furthest = 0 # furthest index reachable with one more jump
for i in range(len(nums) - 1): # stop before the last index
furthest = max(furthest, i + nums[i])
if i == current_end: # the current level is exhausted
jumps += 1
current_end = furthest
return jumpsWhy greedy gives the true minimum
Within a level, it does not matter which index you jump from — all of them cost the same one jump. So the only thing worth optimising is how far the level reaches, and taking the maximum is optimal.
This is BFS's shortest-path guarantee: the first level that contains the destination is the minimum, and levels here are computed exactly, not approximated.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
- Time — one pass, constant work per index. The DP formulation (
dp[i] = min jumps to reach i) isO(n²); explicit BFS with a queue isO(n)time butO(n)space. - Space — three integers, no queue.
Edge Cases
Related Problems
- Jump Game — reachability rather than cost; solve it first
- Binary Tree Level Order Traversal — the explicit BFS that this problem performs implicitly
- Gas Station — another greedy argument about safe skipping