Jump Game II

Medium

The problem

You stand on index 0 of nums. Each nums[i] is the longest jump you can make from index i (shorter jumps are fine too). Return the fewest jumps needed to reach the last index.

Example 1
Input: nums = [2, 3, 1, 1, 4]
Output: 2
Jump from index 0 to 1, then from index 1 to the last index.
Example 2
Input: nums = [2, 3, 0, 1, 4]
Output: 2
Index 0 to 1, then 1 to 4. The 0 in the middle is jumped over.
Example 3
Input: nums = [1, 1, 1, 1]
Output: 3
Each jump moves only one step.

Limits

1 ≤ len(nums) ≤ 100,000
0 ≤ nums[i] ≤ 100,000
The last index is always reachable

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Think in "waves": all positions reachable with one jump, then two jumps, and so on.

The idea

Track the end of the current wave and the farthest reach inside it; when you pass the wave end, take another jump and extend the wave.

Target: O(n) time, O(1) space

Go function shape

func jump(nums []int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// MinJumps: fewest jumps to reach the last index (it is always reachable).
// Greedy BFS-by-ranges: end is the edge of the current jump; farthest is the best edge of the next one.
func MinJumps(nums []int) int {
	jumps, end, farthest := 0, 0, 0
	for i := 0; i < len(nums)-1; i++ {
		farthest = max(farthest, i+nums[i])
		if i == end { // we must jump now: take the best landing we saw
			jumps++
			end = farthest
		}
	}
	return jumps
}

Read the lesson: Greedy