Given an array where each element is the maximum jump length from that index, the machine must return the minimum number of jumps needed to reach the last index. It is guaranteed that the last index is reachable, so the answer always exists.
The key insight is to think in layers rather than individual decisions. All indices reachable in one jump from the current window form the next frontier, so the minimum number of jumps is the number of frontier expansions, which is exactly a breadth-first search over reachability without building the graph.
The approach runs in three steps. First, track the current jump's end boundary and the farthest index reachable from anywhere inside the window. Second, scan left to right, stopping before the last index, and extend the farthest boundary at every position. Third, when the scan crosses the current end, increment the jump count and move the end to the farthest boundary. Time is O(n) and space is O(1).
The trickiest edge case is a single-element array, where the machine is already at the goal and must return 0 jumps — the scan stops before the last index, so the loop never runs. Another trap is that the last index must never trigger a jump count, which is why the scan range is len(nums) - 1.
def jump(nums):
jumps = cur_end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == cur_end:
jumps += 1
cur_end = farthest
return jumps