Jump Game II
MediumGreedy
You are given an integer array nums. You start at index 0, and from index i you may jump forward any number of positions from 1 up to nums[i].
Return the minimum number of jumps needed to reach the last index. The input is guaranteed to allow reaching it. If the array has only one element, you are already there and the answer is 0.
Example 1
- Input:
- nums = [3, 1, 4, 1, 1, 1, 2]
- Output:
- 2
- Explanation
- The first jump can land on index 1, 2, or 3. Landing on index 2 (value 4) lets the second jump reach index 6, the last index, so 2 jumps are enough. One jump cannot reach it.
Example 2
- Input:
- nums = [1, 2, 1, 1, 1]
- Output:
- 3
- Explanation
- Jump to index 1, then jump 2 to index 3, then 1 to index 4: 3 jumps. No route does it in 2, since the first jump can only reach index 1 and from there index 3 at most.
Example 3
- Input:
- nums = [0]
- Output:
- 0
- Explanation
- The start is already the last index, so no jumps are needed.
Constraints
- 1 ≤
nums.length≤ 104 - 0 ≤
nums[i]≤ 1000 - The last index is always reachable