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.

Restating the Problem: You need to find the shortest path to the last index. Because we want the minimum jumps, we want each jump to take us to the most advantageous position for our next jump.

• Constraints to note: The array length can be up to 10^4. An O(n^2) solution will likely fail, so we need O(n).
• Edge cases: If the array has only 1 element [0], you are already at the end and require 0 jumps.

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

Brute Force / DP Approach

The naive approach is to use a 1D DP array where dp[i] stores the minimum jumps needed to reach the end from index i. For each index, you would check all reachable indices i + 1 to i + nums[i] and take the minimum of those values plus 1. This takes O(n^2) time because for each index, you might scan up to n elements ahead. This is too slow.

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.

Code Walkthrough:

• Initialization: jumps counts how many times we've jumped. current_end is the farthest we can reach with our current number of jumps. furthest is the maximum reach we've found so far for the next jump.
• Iteration: We loop from 0 to len(nums) - 2. We stop before the last index.
• Updating Reach: At each index i, we see if i + nums[i] extends our furthest possible reach.
• Taking a Jump (i == current_end): If we reach the end of the current jump's range (current_end), we are forced to take another jump to keep moving. We increment jumps and update current_end to furthest, essentially stepping into the next level of the BFS.

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.

• Time Complexity: O(n). We iterate through the array once. Each step performs a constant amount of work (checking max and simple conditionals).
• Space Complexity: O(1). We only maintain three variables (jumps, current_end, furthest), regardless of input size.

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.