45. Jump Game II — DSA Atlas

MediumGreedy AlgorithmsGreedy interval expansionGreedy BFS by reachable layers

Jump Game II

Given a 0-indexed array nums where nums[i] is the maximum forward jump length from index i, return the minimum number of jumps needed to reach the last index. The test cases guarantee the last index is always reachable.

Open official problem prompt ↗

In plain English

Find the fewest hops that carry you from the first index to the last, where each cell caps how far a single hop can go.

Picture it like this

Like hopping across a river on stones where each stone tells you the maximum distance you may leap: from your current bank you scout every stone you can already reach, remember the one that lets you jump farthest, and only 'spend' a leap when you must cross beyond your current shore.

Example

Input: nums = [2, 3, 1, 1, 4]
Output: 2
Why: Jump 1 step from index 0 to index 1, then 3 steps from index 1 to the last index.

Constraints

1 <= nums.length <= 10^40 <= nums[i] <= 1000It is guaranteed that you can reach nums[n - 1]

Pattern lesson

See the pattern, then code

Greedy BFS by reachable layers

↗

Greedy Algorithms

A locally best action can be justified by an exchange argument or invariant.. Treat each jump as a BFS level: from every index in the current reachable window, note the farthest index you could land on. When you step past the end of the current window, you have spent one more jump and the window extends to that farthest reach.

New words, made simpleKnow these before the algorithm

Reach / farthest: The maximum index you could land on using indices seen so far.
Level boundary: The last index reachable with the jumps already counted; crossing it costs one more jump.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Breadth-first search on indices

Correct but the explicit queue and revisits are wasteful for a line of indices.

Model indices as graph nodes with edges to all reachable indices and BFS for shortest hop count.

Time O(n^2)Space O(n)

DP over minimum jumps

Quadratic and uses extra memory; too slow at n = 10^4 in the worst case.

dp[i] = min jumps to reach i, filled by relaxing each reachable neighbor.

Time O(n^2)Space O(n)

Best choiceGreedy layered reach

Single pass, constant space, and provably optimal.

Sweep once, extending the farthest reach and bumping the jump count only when the current level boundary is crossed.

Time O(n)Space O(1)

The rule we keep true

Invariant

After processing index i, farthest is the maximum index reachable with (jumps + 1) hops, and cur_end is the maximum index reachable with exactly jumps hops.

Why this is correct

Reasoning

The indices reachable with exactly k jumps form a contiguous prefix window. Greedily taking the farthest landing among a window's cells maximizes the next window, and since each window is a superset of what any other choice within that level could reach, the jump count computed is the minimum possible.

The algorithm in three movesSay these aloud before coding

1Track the current jump boundary (end of this level) and the farthest index reachable so far

i=0 boundary=0 -> jumps=1 boundary=2

2Sweep index i from 0 to n-2, updating farthest = max(farthest, i + nums[i])

i=1 farthest=max(2,4)=4

3When i reaches the current boundary, increment the jump count and set boundary = farthest

i=2 boundary reached -> jumps=2 boundary=4

4Return the jump count once the loop ends

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read-

2 · AskStarting state?

3 · Update statejumps=0, cur_end=0, farthest=0

4 · ResultReady to sweep indices 0..3.

Key takeaway

The first jump covers the window [0,2]; index 1 pushes farthest reach to the last index, so a second jump finishes.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 2-4State setup
jumps counts hops taken, cur_end marks the current level's edge, farthest tracks the best reach discovered.
2
Lines 5-6Extend reach
For each index, record the farthest landing spot any cell in this level can offer.
3
Lines 7-9Spend a jump at the boundary
Hitting cur_end means every cell of this level is exhausted, so commit a jump and open the next window to farthest.
4
Lines 10Result
The loop stops before the last index, so jumps already equals the minimum needed to arrive.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single element array returns 0 jumps
A large first value that already reaches the end returns 1
Arrays with zeros in the middle are still solvable because reachability is guaranteed

Common beginner mistakes

Looping through the last index too, which can add a phantom extra jump
Incrementing jumps on every index instead of only at the boundary
Confusing 'farthest reachable' with 'the value at the current index' rather than i + nums[i]

Check your understanding

Why does the loop stop at index n-2 instead of n-1?

Jump Game II

Jump Game II

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Greedy Algorithms