Jump Game

Scan the array while tracking the furthest index you can reach so far. At each position, if the position is beyond the current reach, you are stuck and the answer is no. Otherwise extend the reach with the jump at that position.

def can_reach(steps):
    furthest = 0
    for index, jump in enumerate(steps):
        if index > furthest:
            return False
        furthest = max(furthest, index + jump)
    return True


print(can_reach([2, 3, 1, 1, 4]))
print(can_reach([3, 2, 1, 0, 4]))

The outputs are True and False. In the first array the reachable range grows far enough to cover the last position. In the second, the third position has a jump of one and the fourth has a jump of zero, so the reach never gets past the last index and the answer is no.

The mechanism is that the reach is a running maximum, so it only ever grows. Every position inside the current reach is reachable, because you can reach the position that produced the reach and then walk forward one step at a time through the positions in between. So the single furthest index summarises everything you need to know about the region you have already covered.

The trade-off to name is that this is a greedy scan and it works because reachability is monotonic: being able to reach further never hurts. Contrast it with the dynamic program version, which keeps a boolean per position, and the two agree on every input, which is a good sanity check. The greedy version uses constant space and one pass, which is the better answer, and the failure case is exactly the one the second example shows.

Keep a count of the current boundary, the furthest index reachable with the jumps you have counted so far, and the furthest index reachable with one more jump. When the scan reaches the current boundary, you commit another jump and move the boundary up.

The second version of the same idea uses a breadth first search over the positions, where each position is a state and the edges are the possible jumps. The first version avoids building that graph, which is why it is the one to write in an interview.

The mechanism of the boundary method is that the positions between the current boundary and the next boundary are exactly the ones reachable with one additional jump. Counting how many times you have to cross a boundary is therefore counting the jumps, and the number of boundaries crossed is the answer.

The trade-off to name is that the reachability version and the minimum jumps version need different bookkeeping. The first only cares about the maximum reach, which is a single number, while the second has to track where the current layer ends. Both are linear time and constant space. A breadth first search would also work and would give you the shortest path directly, but it stores the queue of reachable positions, so it uses more space for the same linear time.