Now count the fewest hops to the end. Treat each jump as a window of reachable spots, and only jump when you walk off its edge.
▼The problem
LeetCode 45 (Medium). nums[i] is the maximum jump length from index i. Starting at index 0, return the minimum number of jumps to reach the last index. The last index is always reachable.
Example: [2, 3, 1, 1, 4] → 2 (jump 1 step to the 3, then 3 steps to the end; going 0 → 2 → 3 → 4 takes 3).
The solution
def jump(nums):
jumps = end = farthest = 0
for i in range(len(nums) - 1): # skip the last
farthest = max(farthest, i + nums[i])
if i == end: # window's end
jumps += 1
end = farthest
return jumpsTranscript
Jump Game Two. Same pond, new question. Each number is the farthest you can jump from that spot, and the last index is always reachable. What's the fewest jumps to get there?
Take two, three, one, one, four. Jump to the three, then three more to the end. Two jumps. Hop to the one instead, and it takes three.
You could try every path. Or fill a table of the fewest jumps to each spot, checking every spot before it. That's n squared time.
The greedy trick: think in levels, like breadth-first search. One jump from the start lands anywhere in a window. Two jumps reach the next window, which ends at the farthest any pad in the first window can reach. So walk left to right, tracking the farthest reach. When i hits the window's end, you must jump. Count it, and the next window ends at farthest.
In code, jumps, end and farthest start at zero. Loop up to the second last index, since standing on the last needs no jump. Stretch farthest. If i equals end, add a jump and move end to farthest.
Back to two, three, one, one, four. Index zero reaches two, and it's the window's end. Jump one; the window now ends at two. Index one reaches four. Index two is the end. Jump two; the window ends at four, the last index. Index three changes nothing. Answer: two jumps.
One pass, three numbers. O of n time, constant space.
Don't choose each jump. Fill the window, then leap. That's Jump Game Two.