Can the Last Index Be Reached
Problem
You start at index 0 of a list of non-negative integers. The value at each index is the longest jump you can make from there, so from index i you can land on any index from i + 1 to i + jumps[i]. Return True if you can reach the last index, otherwise False.
Examples
Input: jumps = [2, 3, 1, 1, 4]
Output: True
Why: jump 1 step to index 1, then 3 steps to the endInput: jumps = [3, 2, 1, 0, 4]
Output: False
Why: every route lands on index 3, whose value 0 goes nowhereInput: jumps = [0]
Output: True
Why: edge case, you already stand on the last indexHints
0 / 3
Trying every sequence of jumps explodes. Ask a smaller question instead: how far to the right can you get at all, using any of the indices you can reach?
Scan left to right and keep reach, the farthest index reachable so far. Every index up to reach is reachable, so each one can extend it to i + jumps[i].
If the scan arrives at an index greater than reach, there is a gap you cannot cross and the answer is False. If the scan finishes, the last index was within reach.
Solution
The reachable indices always form one unbroken block starting at 0, because if you can land on index i you can also stop anywhere before your full jump. So the whole state is one number, the right edge of that block. Walking left to right, each index inside the block may push the edge further; the first index outside it proves that nothing beyond can be reached, since no reachable index jumped far enough. That is why the greedy choice is safe: keeping the farthest reach loses no information about which route got there. One pass, O(n) time and O(1) space.
def can_reach_end(jumps):
reach = 0 # farthest index reachable so far
for i, step in enumerate(jumps):
if i > reach: # a gap nobody can jump over
return False
reach = max(reach, i + step)
return True
print(can_reach_end([2, 3, 1, 1, 4])) # -> True
print(can_reach_end([3, 2, 1, 0, 4])) # -> False
print(can_reach_end([0])) # -> TrueStuck on the idea rather than the code? Jump Game covers it.