Description
Each nonnegative array value gives the farthest forward jump from that index. Return the minimum jumps needed to reach the last index. Assume it is reachable.
Solution
def jump(nums):
jumps = end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == end:
jumps += 1
end = farthest
return jumpsExamples
Example 1
- Input
[[2,3,1,1,4]]- Output
2
Jump from index 0 to 1, then to 4.
Example 2
- Input
[[2,3,0,1,4]]- Output
2
The zero can be skipped.
Example 3
- Input
[[0]]- Output
0
You already occupy the last index.
Approach
Scan the range reachable with the current jump count and record the farthest next reach. At the current range's end, commit one jump and extend the range. Do not count a jump after arriving at the last index.
Time & space
O(n) time and O(1) auxiliary space, where n is array length.