Jump Game II
You're given an integer array nums and you start at index 0. nums[i] is your maximum jump length from index i, so from i you can land on any index from i + 1 to i + nums[i]. Return the minimum number of jumps needed to reach the last index. The input always allows reaching the last index, and if the array has only one element you're already there, so the answer is 0.
Examples
nums = [2,3,1,1,4] returns 2
Jump from index 0 to index 1, then 3 steps from index 1 to the last index (4). One jump isn't enough, because index 0 reaches at most index 2.
nums = [2,3,0,1,4] returns 2
Again go 0 -> 1 -> 4, since index 1 (value 3) reaches the end. Index 2 holds 0 and would be a dead end, but you never need to land there.
nums = [0] returns 0
With one element you start on the last index, so no jump is needed.
Constraints
- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 1000
- It's guaranteed that you can reach nums[n - 1].
Hints
Group indices by how many jumps it takes to reach them. Which indices can you reach with 0 jumps, with 1 jump, with 2?
Each group is a contiguous range, so you can sweep the ranges greedily, like levels of a breadth-first search, tracking the farthest reach.
Keep a window [left, right] of indices reachable with the current jump count, starting at [0, 0]. While right is before the last index, scan the window for the max of i + nums[i], move the window to [right + 1, farthest] and add one jump.
Drill This: Your Approach First
Approach
The indices reachable in exactly k jumps form a contiguous range [left, right], like one level of a breadth-first search. Start with [0, 0]. Scan the range for the farthest index any position in it can reach; the next range is right + 1 through that farthest index, and it costs one more jump. Stop once the range covers the last index. Each index is scanned once.
Time
O(n)
Space
O(1)
Pitfall
Solutions
class Solution {
public int jump(int[] nums) {
int jumps = 0;
int left = 0, right = 0;
while (right < nums.length - 1) {
int farthest = 0;
for (int i = left; i <= right; i++) {
farthest = Math.max(farthest, i + nums[i]);
}
left = right + 1;
right = farthest;
jumps++;
}
return jumps;
}
}from typing import List
class Solution:
def jump(self, nums: List[int]) -> int:
jumps = 0
left = right = 0
while right < len(nums) - 1:
farthest = 0
for i in range(left, right + 1):
farthest = max(farthest, i + nums[i])
left, right = right + 1, farthest
jumps += 1
return jumps