Medium BFS Greedy Greedy
In plain English: Find the fewest jumps needed to get from the start to the end of the array.
Think of it as BFS where each 'level' is the farthest you can reach in one more jump. Track the current level's end and the farthest reachable. When you pass the current end, increment jumps.
Prompt
Given an array where each element is the max jump length from that position, return the minimum number of jumps to reach the last index. Assume you can always reach the end.
Try to write it from scratch before scrolling down.
Solution
def jump(nums):
jumps = 0
cur_end = 0
farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == cur_end: # must jump
jumps += 1
cur_end = farthest
return jumps
# Test: jump([2,3,1,1,4]) == 2 (0->1->4)
# Test: jump([2,3,0,1,4]) == 2