You start at index 0 of nums, where nums[i] is the longest forward jump allowed from index i. It is guaranteed that the last index can be reached. Return the minimum number of jumps needed to get there.
- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 1000
- The last index is always reachable
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A DP that, for every index, tries every jump length is O(n * maxJump) or O(n^2). Notice the indices reachable in exactly k jumps form a contiguous window, like a level in BFS. While scanning the current window we compute far, the farthest index any of them can reach; that becomes the end of the next window. The greedy is safe because every index inside a window costs the same number of jumps, so picking the window that reaches farthest can never cost more jumps later.
Algorithm
- Set
jumps = 0,end = 0,far = 0. - For
ifrom 0 ton - 2(we never jump from the last index):far = max(far, i + nums[i]). - If
i == end, the current level is finished:jumps += 1andend = far. - Return
jumps.
O(n)Space: O(1)n - 2. Looping to n - 1 adds an extra jump whenever end lands exactly on the last index, for example [1,2] would give 2 instead of 1.class Solution: def jump(self, nums: List[int]) -> int: jumps = end = far = 0 for i in range(len(nums) - 1): far = max(far, i + nums[i]) # farthest reach of the next level if i == end: # current level finished jumps += 1 end = far return jumps