Fewest hops to reach settlement

Question

You are at stage 0 of a settlement pipeline. From stage i you may advance forward by any amount from 1 up to steps[i] stages. Reach the last stage using the fewest hops. Assume the last stage is always reachable.

steps = [2, 3, 1, 1, 4]
-> 2        # stage 0 -> stage 1 (hop of 1), then stage 1 -> stage 4 (hop of 3)

Return the minimum number of hops to reach the last stage in O(n) time.

Accepted Answer

Think of it as breadth-first search over stages, but done greedily. Sweep left to right tracking farthest, the furthest stage reachable from anything seen in the current hop's "layer", and curend, the boundary of the current layer. When your index reaches curend, you have exhausted the current hop, so spend one more hop and push the boundary out to farthest. Tracing [2, 3, 1, 1, 4]: at i=0 we take hop 1 and curend=2; by i=2 we take hop 2 with farthest=4 = 4, so the answer is 2. Time O(n), space O(1). Edge cases: a single stage needs 0 hops; a 0 in the middle can strand you (the problem here g…

Fewest hops to reach settlement

Your answer

More Coding questions