Jump Game II
Jump Game II: given that you can always reach the last index, return the minimum number of jumps needed.
- 1 <= nums.length <= 10⁴
- 0 <= nums[i] <= 1000
- It's guaranteed that you can reach nums[n - 1].
Intuition
Jump game ii guarantees the last index is reachable and asks for the minimum number of jumps to get there. Reachability is settled; only the count matters.
The insight is to view the array as BFS levels. All positions reachable in one jump form the first level, everything reachable in two forms the second, and so on. The answer is the level containing the last index:
- Track the current level's boundary and the furthest position reachable from anywhere within it; when the boundary is passed, one jump has been used.
Scanning left to right, update farthest = max(farthest, i + nums[i]) at each index. When i reaches the current boundary, the level is exhausted — increment the jump count and set the new boundary to farthest.
That single sweep performs a breadth-first search without a queue, because the levels are contiguous ranges of indices.
The critical detail is the loop bound: iterate to n − 2, not n − 1. Reaching the last index means the journey is complete, and processing it would trigger one final boundary crossing and count a jump that is never taken. This off-by-one gives an answer exactly one too high, and only on inputs where the last index coincides with a boundary — so it passes many tests.
The greedy is optimal because taking the furthest reach at each level is never worse: any position reachable in k jumps is covered by the level-k range, so no better sequence exists.
No jump count is stored per index, so the space stays constant.
A BFS over levels, flattened into one pass. curEnd is the boundary of the current jump's reach; when the scan hits it, a jump must be spent and the boundary moves to farthest. Counting level transitions is the same idea as BFS depth, without the queue.
Approach
Before reading on: price up what the direct approach costs here, then ask why the locally best choice is safe to commit to and never revisit. Aim for O(n) time and O(1) space.
View the array as BFS levels
Positions reachable in one jump form level one, and so on. The answer is the level containing the last index, which a single sweep can compute.
Track boundary and farthest
Keep the current level's end and the furthest index reachable from within it. Two variables replace an explicit queue.
Extend the reach at each index
Update farthest = max(farthest, i + nums[i]). This accumulates the best jump available from anywhere in the current level.
Increment when crossing the boundary
When i reaches the boundary, the level is exhausted — increment the jump count and set the boundary to farthest. That crossing is one jump.
Stop before the last index
Iterate to n - 2, not n - 1. Processing the final index triggers an extra boundary crossing and counts a jump never taken — an off-by-one that passes many tests.
Trust the greedy
Taking the furthest reach per level is never worse, since any position reachable in k jumps lies within the level-k range. No better sequence can exist.
Cost of the scan
One pass with two variables gives O(n) time and O(1) space, with no per-index jump counts stored.
Jump Game II solution in Python | C++ | Java
j jumps forms a contiguous band. Sweep the current band, note the furthest index it can reach, and when the band ends that furthest index becomes the next band's edge — one more jump.0 was the last of the band, so we must jump again — jumps = 1 — and the new band reaches to 2.4; the best in this band is 4.2 was the last of the band, so we must jump again — jumps = 2 — and the new band reaches to 4.j jumps forms a contiguous band. Sweep the current band, note the furthest index it can reach, and when the band ends that furthest index becomes the next band's edge — one more jump.0 was the last of the band, so we must jump again — jumps = 1 — and the new band reaches to 2.4; the best in this band is 4.2 was the last of the band, so we must jump again — jumps = 2 — and the new band reaches to 4.j jumps forms a contiguous band. Sweep the current band, note the furthest index it can reach, and when the band ends that furthest index becomes the next band's edge — one more jump.0 was the last of the band, so we must jump again — jumps = 1 — and the new band reaches to 1.1 was the last of the band, so we must jump again — jumps = 2 — and the new band reaches to 2.2 was the last of the band, so we must jump again — jumps = 3 — and the new band reaches to 3.Common pitfalls
Looping to the last index
for i in range(len(nums)):
for i in range(len(nums) - 1):
Standing on the final index means you've arrived; scanning it can trigger one more i == curEnd bump and return a count one too high. Excluding it makes the boundary logic exact.
Incrementing on every extension
if farthest > curEnd:
jumps += 1if i == curEnd:
jumps += 1
curEnd = farthestA jump is spent only when the current reach is exhausted, not whenever a better landing appears. Counting extensions massively overcounts on arrays with large steps.
Greedily taking the largest single step
i += nums[i] # always jump as far as possible
farthest = max(farthest, i + nums[i])
The longest jump can land somewhere with poor onward reach — on [3, 1, 1, 1, 4] jumping to index 3 is worse than to index 1. The right greedy choice is the furthest reachable frontier over the whole level, not the biggest individual step.
Edge cases
The loop never runs and 0 is returned — you are already there.
One jump, provided nums[0] >= 1, which the problem guarantees.
curEnd immediately covers the end, so the answer is 1.
The classic off-by-one: it counts a phantom extra jump when the last index closes a band. Stopping at n - 2 avoids it.