Greedy: jump game

You're standing on the first tile of a row. Each tile holds a number that is the maximum jump length you can make from it (you may jump anywhere from 0 up to that many tiles forward). Question: can you reach the last tile?

You could throw dynamic programming at this, but there's a cleaner greedy idea. Keep track of the farthest index you can currently reach. Walk left to right, and at each tile:

• If you've already walked past your reach, you're stranded — the answer is False.
• Otherwise, stretch your reach to max(reach, i + nums[i]).

If you make it through the whole array without ever falling behind your reach, the end was reachable.

reach = 0
for i, n in enumerate(nums):
    if i > reach:        # we can't even step onto tile i
        return False
    reach = max(reach, i + n)
return True

The trap tile is a 0 you land on with no momentum to spare — like [3, 2, 1, 0, 4], where your reach maxes out at index 3 and that 0 leaves you stuck one tile short.

Your task

Write can_jump(nums) that returns True if the last index is reachable from index 0, otherwise False. A single tile is trivially "reached."

can_jump([2, 3, 1, 1, 4])   # True   -> 0 -> 1 -> 4
can_jump([3, 2, 1, 0, 4])   # False  -> the 0 at index 3 strands you
can_jump([0])               # True   -> already on the last tile
can_jump([1, 0, 1, 0])      # False  -> index 1 only reaches index 1

Hint: one pass, one variable. The moment your loop index outruns your reach, give up; if you survive the loop, you made it.