Jump Game II

01 · Question

You are given an array nums. Each element represents your maximum jump length. Return the minimum number of jumps to reach the last index.

The array is nonempty, jump lengths are nonnegative, and reaching the last index is guaranteed.

02 · Analysis

Assume a nonempty array of nonnegative jump lengths and that the last index is reachable. Treat each jump count as a BFS layer of reachable positions. Scan the whole current layer to find the next farthest boundary; only then increment jumps. Do not count another jump after reaching the final index. Time O(n), auxiliary space O(1). Without the reachability guarantee, a boundary that cannot advance must report failure.

03 · Solution

Reference solution

1def jump(nums: List[int]) -> int:
2    jumps = 0
3    end = 0
4    farthest = 0
5
6    for i in range(len(nums) - 1):
7        farthest = max(farthest, i + nums[i])
8        if i == end:
9            jumps += 1
10            end = farthest
11
12    return jumps

Jump Game

Gas Station