Fewest Hops to the End
Problem
Each position in a list holds the maximum number of steps you may hop forward from it. You start at position 0 and the last position is always reachable. Return the smallest number of hops that gets you there.
Examples
Input: nums = [2, 3, 1, 1, 4]
Output: 2
Why: hop to index 1, then straight to the endInput: nums = [2, 1, 1, 1, 1]
Output: 3
Why: no single hop covers more than two positions hereInput: nums = [0]
Output: 0
Why: edge case, you already stand on the last positionHints
0 / 3
Trying every hop from every position repeats an enormous amount of work. Ask what all the positions reachable in the same number of hops have in common.
Think of the list as layers: everything reachable in one hop, then everything reachable in two. You only ever need the right-hand edge of the current layer.
Sweep left to right tracking the furthest index the current layer can reach. When the sweep hits the edge of the current layer, count one hop and make the furthest index the new edge.
Solution
Group the positions into layers by how many hops they need; the answer is the number of layers crossed. Walking left to right, keep the furthest index anything in the current layer can reach. Arriving at the current layer's right-hand edge means the layer is exhausted, so one more hop is spent and the frontier becomes the new edge. The loop stops one position early so standing on the last index never costs a hop. Time is O(n) and space is O(1).
def fewest_hops(nums):
hops, edge, farthest = 0, 0, 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i]) # best landing from this layer
if i == edge: # layer exhausted: hop once
hops += 1
edge = farthest
return hops
print(fewest_hops([2, 3, 1, 1, 4])) # -> 2
print(fewest_hops([2, 1, 1, 1, 1])) # -> 3
print(fewest_hops([0])) # -> 0Stuck on the idea rather than the code? Jump Game covers it.