Jump Game II

Jump Game asked whether you can reach the end. Jump Game II asks for the fewest jumps, and it is where many candidates reach for DP. The DP is correct but quadratic. The greedy version keeps the furthest-reach idea and adds one thing: it notices when you have run out of the current jump.

The model to hold in your head is breadth-first search. Index 0 is level 0. Everything one jump away is level 1. Everything two jumps away is level 2. The answer is the level of the last index — and because reachable indices form blocks, you never need a queue.

The problem

Same array as Jump Game: from index i you may jump to any index from i + 1 to i + nums[i]. This time the last index is guaranteed to be reachable. Return the fewest jumps needed to land on it from index 0.

• [2, 3, 1, 1, 4] → 2. Jump 0 → 1, then 1 → 4.
• [1, 2, 1, 1, 1] → 3. Jump 0 → 1, 1 → 3, 3 → 4. No two-jump path exists: after one jump you can only be at index 1, and from there you reach at most index 3.

Constraints: 1 ≤ n ≤ 10⁵, 0 ≤ nums[i] ≤ 10⁵, and the end is reachable.

Clarifying questions

• One element? Zero jumps — you start on the last index.
• Is reaching the end guaranteed? Yes. (If not, return −1; see the follow-ups.)
• Do jumps past the end count? You land on the last index as soon as a jump covers it.
• Return the path or the count? The count.

Approach 1: the simple way

Let best[i] be the fewest jumps to land on i. From every index j, try every jump length and improve the landing index.

1def min_jumps_dp(nums: list[int]) -> int:2    """best[i] = fewest jumps to land on i; try every jump that starts at j."""3    n = len(nums)4    best = [0] + [float("inf")] * (n - 1)5    for j in range(n):6        for step in range(1, nums[j] + 1):7            if j + step < n:8                best[j + step] = min(best[j + step], best[j] + 1)9    return best[n - 1]

This is O(n × max jump) time, O(n²) in the worst case, and O(n) space. With n = 10⁵ and large values that is up to 10¹⁰ updates. The waste is the same as in Jump Game: each index is improved from many earlier indices, and almost all of those updates change nothing.

The key insight

Group indices by how many jumps it takes to reach them. With [2, 3, 1, 1, 4]:

• Level 0: index 0.
• Level 1: everything index 0 reaches — indices 1 and 2.
• Level 2: everything level 1 reaches that is not already in a level — index 1 reaches up to 4, index 2 up to 3, so indices 3 and 4.

Each level is a contiguous range, for the same reason as in Jump Game: if a jump from a level can land on index x, it could also have stopped short. And each level starts right after the previous one ends. So a level is fully described by where it ends, and the next level ends at the furthest reach of any index in the current level.

That gives a one-pass algorithm. Walk the indices. Keep level_end, the last index reachable with the jumps taken so far, and furthest, the last index reachable with one more jump. When i reaches level_end, the current level is used up: take a jump, and the new level ends at furthest.

The greedy choice hidden inside: from the current level, the jump that matters is the one from the index that reaches furthest. Any other index in the level reaches a subset of what that one reaches, so it can never lead to fewer jumps.

Approach 2: optimised — levels without a queue

1def min_jumps(nums: list[int]) -> int:2    """Count jumps as BFS levels: each level is a range of indices."""3    jumps = 04    level_end = 0          # last index reachable with `jumps` jumps5    furthest = 0           # last index reachable with one more jump6    for i in range(len(nums) - 1):     # never jump FROM the last index7        furthest = max(furthest, i + nums[i])8        if i == level_end:             # this level is used up: take a jump9            jumps += 110            level_end = furthest11    return jumps

1. Update furthest from every index in the current level.
2. When i == level_end, every index of the current level has been seen. Spend one jump; the next level ends at furthest.
3. The loop runs to len(nums) - 2. Once you are standing on the last index you do not jump again.

Dry run on [2, 3, 1, 1, 4]:

The loop stops before index 4. Answer 2. Read the table as levels: at i = 0, level 0 ends and level 1 covers indices up to 2. At i = 2, level 1 ends; its best reach was 4 (from index 1), so level 2 covers up to 4, which contains the last index.

Complexity: O(n) time — each index is seen once. O(1) space — three integers.

Why the loop stops early

Suppose the loop ran to the last index. On [2, 3, 1, 1, 4], at i = 4 we would have i == level_end (4 == 4) and count a third jump — a jump from the finish line. Stopping at len(nums) - 1 (exclusive) is how the code says "arriving is enough". It also makes [0] return 0 without special handling: the loop body never runs.

Edge cases

• One element: 0 jumps, the loop never runs.
• A first jump that covers everything, [4, 1, 1, 1, 1]: at i = 0, level_end becomes 4 and no other index equals it: 1 jump.
• All ones, [1, 1, 1, 1]: every index ends a level: 3 jumps.
• Zeros inside a level, [2, 3, 0, 1, 4]: the 0 at index 2 is in level 1 but index 1 already reaches 4: still 2 jumps.

Follow-ups

• What if the end might be unreachable? At i == level_end, after updating furthest, check if furthest <= i: return -1 — the next level would be empty.
• Return the actual jumps? Also remember which index gave furthest in each level; that index is where you jump from.
• Minimum taps to water a garden / video stitching? Convert each tap or clip into "from position a you can reach b", build a furthest-reach array, and run this exact loop.