Fewest hops to the last tile

Greedy choices and intervals Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
hops = [2, 3, 1, 1, 4]
jumps = layer_end = furthest = 0
for i in range(len(hops) - 1):
    furthest = max(furthest, i + hops[i])
    if i == layer_end:
        jumps += 1
        layer_end = furthest
print(jumps)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 2

Right: tile 0 to tile 1, then tile 1 to the end.

Each layer boundary marks one hop, and the furthest reach inside a layer sets the next boundary.

Why not the others?
  • B 3. Hopping to tile 1 first reaches the end in one more hop.
  • C 1. Tile 0 reaches tiles 1 and 2, not the last tile (4), so one hop is not enough.

30-second answer

Think in layers: the tiles reachable with k hops form a range. While scanning the current range, track the furthest tile reachable with one more hop. When the scan reaches the end of the range, take a hop and the new range ends at that furthest tile. O(n) time, O(1) memory.

Practise saying it · 45 s. No recording, just a timer

Explain the fewest-hops layers.

Say your answer out loud, then check which of these points you covered:

  • Layers of reach
  • Hop at the layer end
  • O(n)

Deep dive

This is BFS on a line, with ranges instead of a queue.

Every hop being at least 1 guarantees the end is reachable.

Stop the loop before the last tile; you do not hop from it.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def fewest_hops(hops: list[int]) -> int:
    count = layer_end = furthest = 0
    for i in range(len(hops) - 1):  # no hop needed from the last tile
        furthest = max(furthest, i + hops[i])
        if i == layer_end:  # this layer is done: take a hop
            count += 1
            layer_end = furthest
    return count

Common mistakes

  • Hopping as far as possible from each tile, which is not optimal.
  • Counting an extra hop when the last tile is the end of a range.

Senior take & follow-ups

Explain it as BFS layers; it makes the correctness clear.

Follow-up questions

Think of your answer first, then open the hint.

  1. Why is 'hop as far as possible' wrong?

    Show hint

    A shorter hop can land on a tile with a much bigger hop.

  2. How do you list the tiles landed on?

    Show hint

    Record which tile gave the furthest reach in each layer.

What each operation costs: Merge Sort · Quick Sort

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.