Jump Game II

Counting paths creates noise. Counting how many jumps reach each frontier exposes the structure.

Minimum-jumps table

Dynamic programming (DP) stores answers to smaller versions of a problem so you can reuse them. Here, store the fewest jumps needed to land at each index. For a landing i, inspect every earlier position j; whenever j + nums[j] >= i, j offers a candidate route to i.

def jump(nums: list[int]) -> int:
    n = len(nums)
    min_jumps = [n] * n
    min_jumps[0] = 0
 
    for landing in range(1, n):
        for takeoff in range(landing):
            if takeoff + nums[takeoff] >= landing:
                min_jumps[landing] = min(
                    min_jumps[landing],
                    min_jumps[takeoff] + 1,
                )
    return min_jumps[-1]

Time O(n²) — each landing may inspect every earlier takeoff. Space O(n) for the minimum-jumps table.

Greedy jump layers

All indices reachable with the same number of jumps form a contiguous layer. Scan every index in the current layer and record the furthest position any of them can reach. Once the scan hits the layer's end, one more jump is unavoidable, and that furthest position becomes the next layer's end.

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

Stopping the scan before the last index avoids counting a jump after you've already arrived.

The exchange argument is a proof that replacing a competing choice with the greedy choice can't worsen the result. Suppose an optimal route uses one more jump from the current layer. That jump can reach no farther than the largest endpoint offered anywhere in the layer. Exchange its next frontier for the greedy farthest frontier: every index up to that point is still reachable because shorter jumps are allowed, and no future option is lost. Advancing the widest possible layer is therefore globally optimal, so the first layer that contains the last index uses the minimum number of jumps.

Time O(n) — each index contributes to one layer scan. Space O(1) — the two frontier endpoints and the jump count are enough.