45. Jump Game II
You start on index 0 of an integer array nums. The value stored at a cell is your maximum leap from it: standing on index i, you may jump to any index from i + 1 up to i + nums[i] (you never have to use the full distance). Return the minimum number of jumps required to reach the last index.
The inputs are guaranteed to be winnable — the last index is always reachable. If the array has just one element, you are already standing on the goal and the answer is 0.
Example 1:
Input: nums = [2, 3, 1, 1, 4]
Output: 2
Explanation: Jump from index 0 to index 1 (leap 1 of the allowed 2), then from index 1 leap 3 to index 4, the last index. Two jumps.
Example 2:
Input: nums = [2, 3, 0, 1, 4]
Output: 2
Explanation: The zero at index 2 is a trap, but the route 0 → 1 → 4 never lands on it.
Constraints:
- 1 ≤ nums.length ≤ 10⁴
- 0 ≤ nums[i] ≤ 1000
- The last index is guaranteed to be reachable from index 0.
Hints:
Think in rounds, like BFS on a line: after k jumps you can stand anywhere in some window of indices. The (k+1)-jump window runs from just past the current window to the farthest point any index inside it can reach.
Sweep i from left to right tracking `farthest = max(farthest, i + nums[i])`. When i hits the end of the current window, you are forced to jump: increment the count and extend the window to `farthest`.
Exclude the last index from the sweep — arriving there should not trigger one more phantom jump.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [2, 3, 1, 1, 4]
Expected output: 2