The problem
As in Jump Game, but the last index is always reachable. Return the fewest jumps needed to reach it.
Examples
01
- Input
nums = [2, 3, 1, 1, 4]
- Output
2
02
- Input
nums = [2, 3, 0, 1, 4]
- Output
2
Constraints
- 1 ≤ nums.length ≤ 10⁴
- 0 ≤ nums[i] ≤ 1000
- The last index can be reached.
The idea
Think in rounds, as breadth-first search would: the indices reachable in exactly k jumps form a window. Scanning that window tells you how far k + 1 jumps can reach: the furthest i + nums[i] inside it.
So walk the array once with end, the edge of the current window, and far, the best reach seen. When i reaches end, the window is exhausted: jump (count one) and move end to far. Stop before the last index — standing on it needs no further jump.
- Time
- O(n)
- Space
- O(1)
Solution
class Solution: def jump(self, nums: List[int]) -> int: # Breadth-first in disguise: indices reachable in `jumps` jumps form a window ending # at `end`; scanning it finds how far one more jump can reach (`far`). jumps = end = far = 0 for i in range(len(nums) - 1): far = max(far, i + nums[i]) if i == end: # the window is used up: jump once more jumps += 1 end = far return jumps