Start learning free

LESSON 266 OF 338 · MEMOIZATION

Jump Game II in Go: Minimum Jumps with Memoization

Practice O(n2) - Memoization 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:

Apply memoization to the previous soltuion. Your algorithm should run in O(n^2) time and use O(n) extra space.

STEP 1 OF 8
    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: any distance from 1 up to nums[i] is allowed. The function returns the minimum number of jumps needed to land on the last index.

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

    Approach: minimum over the first jump, remembered

    Think of minJumps(i) as "the fewest jumps to reach the last index when standing on index i". From i you can choose any landing index j from i + 1 to i + nums[i]. Taking that jump costs 1, plus minJumps(j) for the rest, so:

    minJumps(i) = 1 + the smallest minJumps(j) over every reachable j, and minJumps(last) = 0.

    Written as plain recursion, this recomputes the same index over and over. Many different first jumps lead to the same cell, and each time the whole subtree below it is searched again. For inputs where every cell can reach all the cells after it, the number of paths doubles with each extra element, so the running time is exponential.

    The fix is memoization: minJumps(i) depends only on i, so compute it once, store it and reuse it. There are n possible values of i, each costs one loop over at most n choices, giving the O(n^2) time the lesson asks for, with O(n) extra space for the cache. A bottom-up version of the same idea appears in the next lesson on this problem.

    Step by step

    1. Create the cache as a map literal that already holds the base case: the last index maps to 0, since no jumps are needed there. Seeding it means the helper needs no separate base-case check.
    2. Delegate to a helper and return minJumps(nums, 0, cache), the answer from the starting index.
    3. Declare minJumps with the slice, the index i and the cache.
    4. Look in the cache first, using the comma-ok form in the if statement. A hit returns immediately. This covers both earlier results and the seeded last index.
    5. Start result at len(nums). No route needs that many jumps (at most len(nums) - 1), so it works as infinity.
    6. Loop over the landing cells. j runs from i + 1 while it stays inside the slice and within the jump length i+nums[i].
    7. Take the best. For each j, a first jump to j costs 1+minJumps(nums, j, cache). Keep the smaller of that and result.
    8. Save and return. Store result under i so the cell is never solved again.

    The solution in Go

    func jump(nums []int) int {
    cache := map[int]int{len(nums) - 1: 0}
    return minJumps(nums, 0, cache)
}

func minJumps(nums []int, i int, cache map[int]int) int {
    if value, exists := cache[i]; exists {
        return value
    }
    result := len(nums)
    for j := i + 1; j < len(nums) && j <= i+nums[i]; j++ {
        result = min(result, 1+minJumps(nums, j, cache))
    }
    cache[i] = result
    return result
}

    The Go details worth knowing:

    • A map literal as the cache. map[int]int{len(nums) - 1: 0} creates the map and stores the base case in one expression. The key is the index of the last element.
    • Comma-ok. Reading a missing key returns 0, which is also a valid answer here (the last cell needs 0 jumps). value, exists := cache[i] separates the two cases. The value and exists names are scoped to the if statement.
    • The map is shared. A map argument refers to the same underlying table, so every recursive call reads and writes the cache created in jump.
    • The built-in min. Go 1.21 added min and max as built-in functions for ordered types, so min(result, 1+minJumps(nums, j, cache)) needs no import and no hand-written helper.
    • Compound loop condition. j < len(nums) && j <= i+nums[i] stops at the end of the slice even when the jump length reaches past it. The && evaluates left to right, so j < len(nums) is tested first.

    Complexity

    Time: O(n^2). Each index is solved once and then served from the cache. Solving an index runs a loop of at most n - 1 iterations, and each iteration is a cache lookup or the one-time computation of a new index.

    Space: O(n). The cache holds at most n entries, and the recursion goes at most n calls deep: the first branch follows jumps of length 1, so the stack can reach the end of the slice.

    Edge cases and common mistakes

    • One element. [0] returns 0, because the start is already the last index and the seeded cache has the answer.
    • A zero blocks the way. For [1, 0, 1] the last index can't be reached. The loop at a zero cell never runs, so that cell keeps the "infinity" value len(nums), and the function returns len(nums), which is 3 here. The lesson's problem assumes the last index can be reached, so this case doesn't arise in the tests; code that must handle it should check for that value.
    • Using 0 as "not cached". A stored 0 is a real answer for the last cell. The comma-ok test avoids confusing it with a missing key.
    • Looping past the slice. Without j < len(nums), a large nums[i] indexes beyond the end and panics.
    • Starting j at i. The cell would call itself with no progress and recurse forever.
    • Forgetting to store the result. The code still returns correct answers, but the cache never fills and the running time becomes exponential again.

    Testing

    • [2, 3, 1, 1, 4] gives 2.
    • [2, 3, 0, 1, 4] gives 2.
    • [1, 1, 1, 1] gives 3.
    • [5, 1, 1] gives 1.
    • [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