Jump Game II

Problem

You are on the first cell of an integer array nums, where nums[i] is the maximum forward distance you can jump from cell i. It is guaranteed that the last cell is reachable. Return the minimum number of jumps needed to get from the first cell to the last.

• nums has between 1 and 50,000 cells.
• Each value is a non-negative integer no larger than 5,000.
• The last index is always reachable.

Examples

• nums = [3, 1, 1, 4, 2, 1, 1] → 2. Jump 3 to index 3, then 3 more to the end.
• nums = [1, 2, 1, 1, 1] → 3. Index 0 to 1, then 2 to index 3, then 1 to the end; no cell has enough reach to save a jump.
• nums = [6] → 0. Already at the end, no jumps needed.

Hints

1. Think of each cell as a node with edges to the cells it can jump to. What algorithm gives the fewest edges in an unweighted graph?
2. Every cell reachable in j jumps forms a contiguous range. Why? What are the endpoints of the range for j + 1 jumps?
3. Greedy sweep: track the end of the current jump's range and the farthest cell any position in that range can reach; when the sweep passes the current range's end, count a jump and adopt the farthest as the new end.