4.26.3 — Jump Game II

LeetCode 45 · Medium

The problem

Same array as 4.26.2 — nums[i] is the maximum jump length from index i. You are guaranteed the end is reachable. Return the minimum number of jumps to get there.

[2,3,1,1,4]   →  2     (index 0 → 1 → 4)
[2,3,0,1,4]   →  2

The pattern

"Fewest steps" says BFS, and that instinct is right — but you do not need a queue.

Think of the indices in levels, exactly like a breadth-first search:

• Level 0 — index 0.
• Level 1 — everything reachable in one jump from level 0.
• Level 2 — everything reachable in one jump from anything in level 1.

The number of jumps is the level the last index lands in.

And because reachability is downward closed (the argument from 4.26.2), each level is a contiguous range of indices. So a level is described by two numbers — where it ends, and how far the next level reaches — and no queue is needed.

That is the whole solution: sweep left to right, and every time you reach the end of the current level, take a jump.

The solution

Python

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = 0
        current_end = 0        # last index of the current level
        furthest = 0           # furthest index the next level reaches

        for i in range(len(nums) - 1):        # note: stop BEFORE the last index
            furthest = max(furthest, i + nums[i])

            if i == current_end:              # level exhausted → must jump
                jumps += 1
                current_end = furthest

        return jumps

TypeScript

function jump(nums: number[]): number {
  let jumps = 0, currentEnd = 0, furthest = 0;

  for (let i = 0; i < nums.length - 1; i++) {
    furthest = Math.max(furthest, i + nums[i]);

    if (i === currentEnd) {
      jumps++;
      currentEnd = furthest;
    }
  }

  return jumps;
}

Three details, and each one matters.

The loop stops at len(nums) - 1, not at the end. Standing on the final index means you have arrived, so no jump is taken from it. Including it would count one jump too many — this is the off-by-one this problem is built around.

furthest accumulates across the whole level before it is used. That is what makes the choice optimal: when the jump is finally taken, it goes to the best possible landing area reachable from anywhere in the current level, not just from the position where the decision was made.

i == current_end is the trigger. You have walked to the last index of the current level, so any further progress needs another jump.

Trace

[2,3,1,1,4]

i	i + nums[i]	furthest	at level end?	jumps	new end
0	2	2	yes (0 == 0)	1	2
1	4	4	no	1	2
2	3	4	yes (2 == 2)	2	4
3	—	—	loop stops at index 3 (len-1 = 4)

Answer 2 ✓.

Notice index 1 contributed furthest = 4 while the jump was not taken until index 2. That is the point of accumulating first — the jump made at index 2 uses the reach discovered at index 1.

Why greedy is optimal here

The exchange argument: suppose an optimal solution uses jump k to land somewhere inside the range that greedy's jump k covers. Since greedy's jump reaches at least as far, you can replace the optimal jump with greedy's without ever needing more jumps later — everything the optimal solution could reach afterwards, greedy can also reach.

"Greedy's reach after k jumps is at least as large as any strategy's reach after k jumps." By induction, greedy never needs more jumps.

That is the shape of a greedy proof: show the greedy state dominates every alternative at each step. 4.25 formalises it.

Complexity

O(n) time, O(1) space.

The DP version — dp[i] = fewest jumps to reach i — is O(n^2) and O(n) space. Write the greedy.

Where this goes next

• Jump Game — can you get there at all. 4.26.2.
• Minimum Number of Taps to Water a Garden and Video Stitching — identical structure in interval clothing. Each tap or clip covers a range; you want the fewest ranges covering [0, n]. Convert each to "furthest reach from position i" and this exact loop solves them. Recognising that these are Jump Game II is worth more than either solution.
• Jump Game VI — a maximum over a sliding window of previous states, which needs a monotonic deque (4.6.6).

What the interviewer will push on

"Why does the loop stop one short?" Arriving at the last index means you are done; no jump is taken from it.

"Why accumulate furthest before jumping?" So the jump uses the best reach available anywhere in the current level.

"Prove the greedy is optimal." Greedy's reach after k jumps dominates any other strategy's reach after k jumps.

"How is this BFS?" Levels are jump counts, and because each level is a contiguous range, two integers replace the queue.

"What is the DP version?" O(n^2) — and say why the greedy beats it.

One thing to volunteer: describe it as BFS without a queue. That framing explains both the level structure and why the answer is the level number, and it makes the two-variable code look inevitable rather than clever.

Next: 4.26.4 Gas Station — a greedy whose proof is the entire problem.