How do you solve the jump game, where each position tells you how far you can jump?
You keep the furthest place that you can reach, and you check that every position you are standing on is inside that range.
def can_reach(steps):
furthest = 0
for index, jump in enumerate(steps):
if index > furthest:
return False
furthest = max(furthest, index + jump)
return True
So how does it work? The variable furthest is the furthest place you could have got to using the positions you have already looked at. At each position you check whether that position is reachable, and if it is not then there is a gap that you cannot cross, so the answer is no.
And then you update the furthest place, because from this position you can jump up to index + jump places forward.
the steps 2, 3, 1, 1, 4
the furthest
index 0 0, then the furthest becomes 2
index 1 1 is inside 2, the furthest becomes 4
index 2 2 is inside 4, the furthest becomes 4
index 3 3 is inside 4, the furthest becomes 5
index 4 4 is inside 5, the furthest becomes 8
the answer is True, because the last index is 4 and the
furthest is 8
And the complexity is O of n for the time and O of 1 for the space. There is no table and no recursion.
And the condition if index > furthest: return False is the heart of it. If you ever stand on a position that you cannot reach, then no later position can be reached either, because every route to a later position has to pass through this one. So you can stop straight away.
So the rule to remember is this. If you stand on a place you cannot reach, then you cannot reach the end.
The last question in this topic shows the version that also counts the jumps.