Description
From index zero, each nonnegative entry is the maximum forward jump length. Decide whether the last index is reachable.
Solution
def can_jump(nums):
farthest = 0
for i,value in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest,i+value)
return TrueExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[2,0,1]]- Output
true
The first jump can reach the last index directly.
Example 2
- Input
[[1,0,2]]- Output
false
The zero at index one blocks the final index.
Example 3
- Input
[[0]]- Output
true
The start is already the destination.
Approach
Scan reachable positions while extending the farthest reachable boundary.
Time & space
O(n) time; O(1) space. Here n is the input length.