Can you hop to the last tile?

Greedy choices and intervals Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
hops = [3, 2, 1, 0, 4]
reach = 0
for i, h in enumerate(hops):
    if i > reach:
        print("stuck at", i)
        break
    reach = max(reach, i + h)
else:
    print("made it")

Options

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

Show answer

Answer: A stuck at 4

Right: every route lands on tile 3, which has a hop of 0.

Reachable tiles always form one unbroken prefix, so one value tracks them all.

Why not the others?
  • B made it. Tile 4 is never reachable here.
  • C stuck at 3. Tile 3 itself is reachable; it is tile 4 that is not.

30-second answer

Track the furthest tile you can reach so far. Walk the tiles in order; if the current tile is beyond that reach, you are stuck. Otherwise update reach = max(reach, i + hops[i]). One pass, O(n) time, O(1) memory.

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

Explain the furthest-reach greedy.

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

  • Track furthest reach
  • Stuck if i > reach
  • O(n)

Deep dive

The 'furthest reach' greedy replaces an O(n²) DP over tiles.

Stopping early once reach covers the last tile is a small win.

Zeros are the only way to get stuck.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def can_reach_end(hops: list[int]) -> bool:
    furthest = 0  # every tile up to here can be reached
    for i, h in enumerate(hops):
        if i > furthest:
            return False
        furthest = max(furthest, i + h)
    return True

Common mistakes

  • Trying every hop length with recursion, which is exponential without a cache.
  • Checking the reach after updating it, which hides a stuck tile.

Senior take & follow-ups

Explain why one furthest value captures all reachable tiles: reachability is a prefix.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you find the fewest hops?

    Show hint

    BFS in layers: each layer is the range reachable with one more hop.

  2. What if hops can go backwards too?

    Show hint

    Then it is a graph search (BFS) over tiles.

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.