LESSON 336 OF 338 · GRAPHS

Jump Game in Go: Minimum Jumps in O(n) with a Moving Pointer

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
             Jump 1 step from index 0 to 1, then 3 steps to the last index.

STEP 1 OF 6

Guided

Ctrl + Enter to check

GO · GRAPHS

Jump Game in Go, explained

Problem overview

The function jump receives a slice of non-negative integers, nums. You start at index 0, and nums[i] is the farthest you can jump forward from index i: any distance from 1 up to that value is allowed. The function returns the minimum number of jumps needed to land on the last index.

In the example nums = [2, 3, 1, 1, 4], the answer is 2. Jump one step from index 0 to index 1, then three steps from index 1 to index 4. A single jump isn't enough, because nums[0] is only 2.

Approach: fill in the cheapest cost of each cell, left to right

Let dp[k] be the minimum number of jumps needed to reach index k. Then dp[0] is 0, and the answer is dp[len(nums)-1].

A direct way to fill dp is to give each cell the best value over every earlier cell that can reach it. That works, but it compares many pairs of cells. A single observation removes the extra work: dp never decreases from left to right. A cell further to the right can't be reached in fewer jumps than a cell to its left, because the route to the right cell contains a jump that starts left of the earlier cell and lands on it or beyond it, and a jump can always be shortened to land exactly there. So the first cell that can reach a new cell gives the best value for it, and later cells can't improve on it.

That suggests a second pointer, j, the first cell not yet reached by any jump. Cell i can reach everything up to index nums[i] + i. Any cell between j and that limit is reached for the first time from i, so its cost is dp[i] + 1, and j moves past it. Because j only moves forward and i only moves forward, one pass over the slice is enough.

Here is the idea on [2, 3, 1, 1, 4]:

At i = 0, the reach is index 2. Cells 1 and 2 get cost 1, and j becomes 3.
At i = 1, the reach is index 4. Cells 3 and 4 get cost dp[1] + 1, which is 2, and j becomes 5.
The remaining positions find j beyond the end of the slice and change nothing. dp is [0, 1, 1, 2, 2].

Step by step

Create dp with make([]int, len(nums)). A new slice is filled with zeros, which is already right for dp[0]. Every other cell is overwritten the first time it is reached.
Declare j as 1, the first cell that no jump has reached. Cell 0 is the starting point.
Loop over every index i of nums with the three-part for.
Add an inner loop with only a condition, Go's form of while. It keeps going while j is within reach of i, j <= nums[i]+i, and still inside the slice, j < len(nums).
Inside it, give cell j its cost, dp[i] + 1, then advance j. In Go j++ is a statement, so it goes on its own line and can't be used inside an expression.
Return dp[len(nums)-1], the cost of the last cell.

The solution in Go

func jump(nums []int) int {
    dp := make([]int, len(nums))
    j := 1
    for i := 0; i < len(nums); i++ {
        for j <= nums[i]+i && j < len(nums) {
            dp[j] = dp[i] + 1
            j++
        }
    }
    return dp[len(nums)-1]
}

The Go details worth knowing:

make zeroes the slice. make([]int, n) gives a slice of length n where every element is 0, so no loop is needed to initialise dp.
Two loops, one pointer. The inner loop doesn't restart j for each i. Since j was declared outside both loops, it keeps its value from one i to the next.
The bound on j. The check j < len(nums) in the loop condition is what keeps dp[j] inside the slice when a jump reaches past the last index.
No while in Go. A for with just a condition does the same job.

Complexity

Time: O(n). The outer loop runs n times. The inner loop looks like it could multiply that, but j never goes backwards and stops at n, so the body of the inner loop runs at most n - 1 times across the entire call. Everything adds up to a linear amount of work, compared with O(n²) for checking every earlier cell for every cell.

Space: O(n). The dp slice has one entry per cell.

Edge cases and common mistakes

A single element. For [0] you're already on the last index, and the function returns 0. The inner loop never runs, because j is 1 and the slice has length 1.
A first jump that covers everything. For [10, 1, 1] the reach of cell 0 is far past the end. The check j < len(nums) stops j at the end, so no index goes out of range, and the answer is 1.
Zeros in the middle. For [2, 3, 0, 1, 4] the cell with value 0 reaches nothing, but cell 1 already covers the cells after it, and the answer is 2.
Single steps. For [1, 1, 1, 1] every jump moves one cell, so the answer is 3.
Dropping the bound on j. Without j < len(nums), a large nums[i] writes past the end of dp and the program panics with an index out of range.
Writing dp[j] = dp[j-1] + 1. Cell j is reached from cell i, which can be far to its left, not from its neighbour.
Unreachable endings. This solution relies on the last index being reachable. For [0, 1] it returns 0, the initial value of the unreached cell, which is not a real jump count. An input like that has to be excluded or handled separately.
An empty slice. dp[len(nums)-1] would be dp[-1], which panics. The problem always starts you on a first index, so the slice has at least one element.

Testing

[2, 3, 1, 1, 4] gives 2.
[2, 3, 0, 1, 4] gives 2.
[0] gives 0.
[1, 1, 1, 1] gives 3.
[10, 1, 1] gives 1.

Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free