Jump Game II

Do not choose the next index. Choose the next reachable frontier.

The common mistake in a Jump Game II solution is to commit too early: “From this index, which landing position should I choose?” That creates a path-search problem. The better question is broader:

Which indices can I reach with the current number of jumps, and how far can the next jump layer extend?

That shift turns the problem into a compact range frontier algorithm. Scan every index in the current frontier, record the farthest next reach, and increase the jump count only when the frontier ends.

The contract and the frontier reframe

You receive a 0-indexed array nums.

• nums[i] is the maximum forward distance from index i.
• From i, you may move to any valid index from i + 1 through i + nums[i].
• You start at index 0.
• You must return the minimum number of jumps needed to reach index n - 1.
• The target is guaranteed to be reachable.
• If n == 1, you are already at the target, so the answer is 0.

For example:

nums = [2, 3, 1, 1, 4]

From index 0, one jump can reach indices 1 or 2. Those two positions form the first useful frontier: every one of them costs one jump to reach.

Now inspect both positions before deciding how many jumps are needed next:

• From index 1, the next reach is 4.
• From index 2, the next reach is 3.

The best next frontier ends at index 4, so the target is reachable in a second jump.

This is the important distinction from the related reachability version of Jump Game: that problem asks whether the final index can be reached at all. Here, reachability is guaranteed; the job is to count the smallest number of frontier layers needed to contain the target.

Recognize the greedy structure

Several signals point toward a minimum-jumps greedy solution:

1. Movement is only forward.
2. Each position offers an interval of possible next positions.
3. Every jump has the same cost: one.
4. The objective is the fewest steps, not the largest jump or a particular landing position.

A recursive solution can try every possible landing index. A dynamic programming solution can store the minimum jumps from each position. Both are valid ways to describe the problem, but they track more detail than the linear greedy method needs.

The repeated work comes from treating paths separately. Many different paths reach the same region of the array. Once positions are reachable with the same number of jumps, their individual histories no longer matter for the next decision. What matters is the farthest index any of them can extend to.

That gives the correct greedy model:

Do not greedily choose the index with the largest nums[i]. Greedily choose the farthest boundary reachable from the entire current frontier.

Those are different decisions.

Suppose the current frontier contains indices 1 through 3. Choosing index 1 immediately because it has a large jump may work, but it is unnecessary reasoning. Scan indices 1, 2, and 3; keep the maximum reach among all of them; then advance the frontier once. The range is the decision unit.

Derive the three variables

The implementation needs only three pieces of state.

current_end

current_end is the last index reachable using the current number of jumps.

Initially:

current_end = 0

With zero jumps, only the starting index is reachable.

If the first jump expands the frontier to index 2, then every index through 2 belongs to the current one-jump layer.

farthest

farthest is the farthest index reachable with one additional jump from any position scanned in the current frontier.

At each index i, update it with:

farthest = max(farthest, i + nums[i])

This summarizes all candidate next landings without storing them.

jumps

jumps counts how many frontier layers have been crossed.

It does not increase at every index. All indices inside the same frontier have already been reached with the same number of jumps. Incrementing at every index would count positions, not jumps.

The boundary event is the key:

if i == current_end:
    jumps += 1
    current_end = farthest

When the scan reaches current_end, the current layer is exhausted. Every position available with the current jump count has now been inspected, so we must cross into the next layer.

Scan only through n - 2, not the final index. The target is where we need to arrive; it does not need to launch another jump.

The minimum-jump invariant

The algorithm is easy to write and easy to get subtly wrong. The invariant explains why the boundary update is safe.

While scanning the current frontier, every processed index is reachable using at most jumps jumps, and farthest stores the best reach available using one additional jump from the scanned frontier.

This invariant has three consequences.

The entire frontier must be scanned

Suppose current_end == 3. Indices 0 through 3 are reachable within the current layer, depending on the current iteration. Before advancing the boundary, we must inspect every relevant index in that range.

Any of those indices might provide the best next reach. Stopping at the first promising index can miss a farther extension later in the same layer.

The boundary advances only after the layer ends

When i == current_end, there are no more positions in the current frontier to inspect. At that point, farthest includes every next-layer option discovered from that frontier.

Setting:

current_end = farthest

selects the largest safe boundary. A shorter boundary cannot give access to anything that the longer boundary does not already include. Since movement is forward, extending farther dominates stopping earlier for purposes of future reach.

The first layer containing the target is optimal

Think of each jump count as a layer:

• Layer 0: the starting index.
• Layer 1: every index reachable in one jump.
• Layer 2: every index reachable in two jumps.
• And so on.

The algorithm finishes processing one layer before entering the next. Therefore, it cannot count k jumps while skipping an index that was reachable in fewer than k jumps.

The first layer whose boundary reaches n - 1 is consequently the minimum-jump layer.

This resembles breadth-first search, where nodes are processed level by level. The difference is that the reachable nodes here form forward intervals, so we can represent an entire BFS layer with two boundaries instead of a queue of individual positions.

The frontier boundary proves the jump count.
The farthest reach preserves the best option for the next layer.

Dry-run: frontier expansion

Use:

nums = [2, 3, 1, 1, 4]

The loop scans indices 0 through 3.

i	nums[i]	farthest after update	current_end before boundary check	jumps after check	Event
0	2	2	0	1	First frontier ends; expand to 2
1	3	4	2	1	Extend the next reach to 4
2	1	4	2	2	Current frontier ends; expand to 4
3	1	4	4	2	Still inside the current frontier

At index 0, the starting frontier ends immediately. We have discovered that one jump can reach through index 2, so jumps becomes 1.

At index 1, the algorithm sees a reach of 1 + 3 = 4. It records that as the best possible next boundary.

At index 2, the one-jump frontier is exhausted. Since all of its positions have now been considered, the algorithm commits to the next boundary, index 4, and increments the count to 2.

The result is:

2

One valid path is:

0 -> 1 -> 4

Now consider:

nums = [2, 3, 0, 1, 4]

The zero at index 2 does not break the solution. Index 1, which belongs to the same frontier, already extended farthest to 4. A weak implementation may see the zero and treat it as a dead end. The frontier model does not: it evaluates the whole layer before making a decision.

Two ordering mistakes are especially common:

1. Testing the boundary before updating farthest.
   The current index may be the position that extends the next frontier. Update its reach first.

2. Scanning the final index as a launch point.
   The answer counts jumps needed to arrive at the target. There is no reason to jump from the target, so stop at n - 2.

Implement the Python solution

Here is the boundary-driven implementation:

def jump(nums: list[int]) -> int:
    jumps = 0
    current_end = 0
    farthest = 0

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])

        if i == current_end:
            jumps += 1
            current_end = farthest

    return jumps

Each line maps directly to an obligation:

• jumps counts completed frontier layers.
• current_end marks where the current layer stops.
• farthest summarizes the best boundary available from that layer.
• range(len(nums) - 1) excludes the target from launch positions.
• The reach update comes before the boundary check, so the current index contributes to the next frontier.
• The boundary check increments the count once per layer, not once per index.

The one-element case works naturally. If nums has length 1, then:

range(len(nums) - 1)

becomes:

range(0)

The loop runs zero times, and jumps remains 0.

The problem guarantees that the target is reachable, so this implementation does not need a separate failure return. In a different problem contract without that guarantee, you would need to detect a dead zone: a point where i == current_end but farthest == i. That is outside this problem's required return behavior, but it is an important boundary to recognize when adapting the pattern.

An equivalent implementation may return early once farthest reaches the target. That can be correct, but it changes the control flow. The boundary-driven version is my preferred interview implementation because its counting rule stays visible: scan the layer, then cross the boundary.

Complexity and edge cases

The time complexity is O(n).

The loop visits each index before the target once. Each visit performs constant-time arithmetic, a maximum comparison, and possibly one boundary update. The array values may represent large jump lengths, but the algorithm never iterates over every possible landing position.

The auxiliary space complexity is O(1). It stores only three scalar variables.

Check these cases during an interview:

Case	Expected reasoning
[0]	Already at the target; answer 0
[1, 1]	One jump reaches the final index
[5, 1, 1, 1]	A direct first jump reaches the target; answer 1
[1, 1, 1, 1]	The frontier advances one index at a time
[2, 3, 0, 1, 4]	The zero is harmless because another index in the frontier extends reach
Any guaranteed-reachable input	No unreachable-state branch is required

Under interview pressure, explain the solution in this order:

1. “I will treat positions reachable with the same jump count as one frontier.”
2. “current_end is the end of the current frontier.”
3. “farthest is the best boundary the next jump can reach.”
4. “I update farthest before checking the boundary so the current index is included.”
5. “When the boundary ends, I increment the jump count and move it to farthest.”
6. “The first frontier that contains the target is minimal because earlier frontiers have already been fully processed.”

That explanation is stronger than saying “we greedily jump as far as possible.” The latter is vague and can suggest the wrong strategy of selecting one index too early.

The reusable rule is precise:

When forward moves create overlapping intervals with equal step cost, identify the current reachable layer, scan the whole interval, summarize the farthest next reach, and advance the boundary only when the layer ends.

Find the layer. Track its boundary. Preserve the next frontier. Let the invariant do the arguing.