Fewest jumps to the end
Reach the last cell in the fewest jumps by treating each jump as a window of cells and always extending to the farthest cell seen in the current window. About 18 minutes.
Windows of cells
Now the end is always reachable, and you want the fewest jumps. Think in rounds. With zero jumps you stand on cell 0. With one jump you can land anywhere up to the reach of cell 0. With two jumps, anywhere up to the best reach from any cell in that first window.
Each round is a window of cells, and the answer is the first round whose window covers the last cell.
One pass, no extra memory
Scan the cells while keeping two numbers: the edge of the current window, and the farthest reach seen so far from any cell scanned.
When the scan arrives at the edge of the window, a new jump must be taken, so add one and move the edge to the farthest reach. Stop before the last cell, since landing on it needs no further jump.
far = max(far, i + nums[i])
Window edge 0, reach 3. At the edge: one jump, the new edge is 3.
Jumps 1, 1, 1, 1. How many jumps to the last cell?
- A3
- B4
- C1
Show the answer
3. Each cell allows only one step, so three single steps are needed.
Fewest jumps
You stand on the first cell of nums, where nums[i] is the longest jump from cell i, and any shorter jump is allowed. The last cell is always reachable. Return the fewest jumps needed to reach it.
nums = [2, 3, 1, 1, 4] → 2
1 ≤ nums.length ≤ 100,000 · 0 ≤ nums[i] ≤ 100,000 · the last cell is always reachable