Start learning free

LESSON 267 OF 338 · MEMOIZATION

Jump Game III in Go: Iterative Bottom-Up Dynamic Programming

Practice O(n2) - DP Read the full explanation

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.

Note:

Convert the previous solution to an iterative one. Your algorithm should run in O(n^2) time and use O(n) extra space.

STEP 1 OF 6
    Ctrl + Enter to check

    GO · MEMOIZATION

    Jump Game in Go, explained

    Problem overview

    The function jump receives a slice nums of non-negative integers. You start at index 0, and nums[i] is the farthest you can jump forward from index i. The function returns the minimum number of jumps needed to reach the last index.

    For nums = [2, 3, 1, 1, 4] the answer is 2: jump from index 0 to index 1, then from index 1 to index 4, the last index.

    Approach: fill a table from right to left

    Let dp[i] be the minimum number of jumps from index i to the last index. The last cell needs 0 jumps. For any earlier cell, the first jump lands on some j between i + 1 and i + nums[i] and the rest of the trip costs dp[j], so:

    dp[i] = 1 + the smallest dp[j] over every reachable j.

    The memoized recursion from the previous lesson computes the same values on demand, starting at index 0 and working outward. The iterative version turns this around. Every dp[i] depends only on cells to its right, so if the table is filled from the last index down to index 0, each value is final by the time a cell needs it. No recursion and no map are needed: the table is a slice, and the call stack stays flat.

    Both versions cost O(n^2) time and O(n) space. The iterative one avoids deep recursion and the overhead of map lookups.

    On [2, 3, 1, 1, 4] the table starts as [5, 5, 5, 5, 0]. Index 3 can reach index 4, so dp[3] = 1. Index 2 can reach only index 3, so dp[2] = 1 + 1 = 2. Index 1 can reach indices 2, 3 and 4 with costs 3, 2 and 1, so dp[1] = 1. Index 0 can reach indices 1 and 2 with costs 2 and 3, so dp[0] = 2. The final table is [2, 1, 2, 1, 0] and the function returns 2.

    Step by step

    1. Allocate the table with make([]int, len(nums)). Every entry starts at 0.
    2. Set every entry to "infinity". A loop writes len(nums) into each cell. No real route needs more than len(nums) - 1 jumps, so this value loses to any real count. Go has no built-in call to fill a slice, hence the loop.
    3. Set the base case: dp[len(nums)-1] = 0.
    4. Loop i downward from len(nums) - 2 to 0. The last cell is already done.
    5. Loop over the landing cells. j runs from i + 1 while j < len(nums) and j <= i+nums[i].
    6. Relax. A first jump to j costs 1 + dp[j], so dp[i] becomes the smaller of its current value and that count.
    7. Return dp[0], the answer from the starting cell.

    The solution in Go

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

    The Go details worth knowing:

    • make gives zeros. A new []int is full of 0, which would look like "no jumps needed" for every cell. The loop that writes len(nums) replaces those zeros before any comparison happens.
    • Counting down. The loop for i := len(nums) - 2; i >= 0; i-- uses a signed int, so the condition i >= 0 works. In an unsigned type, i >= 0 would always be true and the loop would wrap around. Go's int is signed, so there is no such problem here.
    • The built-in min. Since Go 1.21, min is a built-in function, so min(dp[i], 1+dp[j]) needs no import.
    • One loop keyword. Go has no while. The three loops here are all for, and the inner loop's condition combines two tests with &&, which stops at the first false test, so dp[j] is never read beyond the slice.
    • Writing in place. The table is a slice, so dp[i] = ... updates the element directly; no pointer is needed.

    Complexity

    Time: O(n^2). The outer loop runs about n times and the inner loop at most n - 1 times. Building the table costs O(n) more.

    Space: O(n). The only extra memory is dp, one integer per cell. There is no recursion, so no stack growth either.

    Edge cases and common mistakes

    • One element. With [0] the table has one cell, set to 0, and the loop from len(nums) - 2 = -1 never runs. The function returns 0.
    • Empty input. dp[len(nums)-1] becomes dp[-1], which panics with an index out of range error. The lesson's inputs are never empty.
    • A zero blocks the way. For [1, 0, 1] the last cell can't be reached. The cell with the zero keeps the value len(nums), and so does the first cell: the function returns 3. The lesson's problem assumes that the last index is reachable.
    • Filling left to right. The cells to the right would still hold the "infinity" value when they are needed, and the answers would be wrong.
    • Forgetting the initial values. Leaving the zeros in place makes min keep 0 in every cell, so the function returns 0 for any input.

    Testing

    • [2, 3, 1, 1, 4] gives 2.
    • [1, 1, 1, 1] gives 3.
    • [5, 1, 1] gives 1.
    • [2, 3, 0, 1, 4] gives 2.
    • [0] gives 0.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free