Start learning free

LESSON 268 OF 338 · MEMOIZATION

Minimum Path Sum II in Go: Memoized Recursion on a Grid

Practice O(n2) - Memoization Read the full explanation

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

Note:

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

STEP 1 OF 7
    Ctrl + Enter to check

    GO · MEMOIZATION

    Minimum Path Sum in Go, explained

    Problem overview

    The function minPathSum receives a grid of non-negative integers as a [][]int. A path starts at the top-left cell, ends at the bottom-right cell, and each step moves either down or right. The function returns the smallest possible sum of the numbers on a path, counting both end cells.

    For the grid [[1,3,1],[1,5,1],[4,2,1]] the answer is 7, from the path 1, 3, 1, 1, 1: right, right, down, down. Every other path costs more.

    Approach: best path from a cell, remembered

    Define minSum(i, j) as the cheapest path from cell (i, j) to the bottom-right corner. Standing on (i, j) you pay grid[i][j], then move down to (i+1, j) or right to (i, j+1) and take the cheaper of the two continuations:

    minSum(i, j) = grid[i][j] + min(minSum(i+1, j), minSum(i, j+1))

    At the bottom-right cell the path is that single cell, so the answer is grid[i][j]. Without any caching, this recursion explores every path, and the number of paths grows exponentially with the grid size. But a cell can be reached from many directions, and minSum(i, j) doesn't depend on how you got there. Memoization stores each cell's answer in a table the same size as the grid, so each cell is solved once.

    With m rows and n columns there are m * n cells, each solved in constant time once its neighbours are known. That gives the O(m * n) time and O(m * n) space the lesson asks for.

    Step by step

    1. Build the cache. cache has the same dimensions as grid and starts filled with zeros. The lesson provides a makeMatrix(rows, cols) helper for this; the number of columns comes from the first row, len(grid[0]).
    2. Delegate and return minSum(grid, cache, 0, 0), the answer from the start cell.
    3. Declare minSum with grid, cache [][]int and i, j int, returning an int.
    4. Handle cells outside the grid. When i or j is past the last row or column, return math.MaxInt, the largest int. A path that leaves the grid then loses every comparison.
    5. Handle the target. At the bottom-right cell, return grid[i][j].
    6. Check the cache. A positive cache[i][j] is a stored answer, so return it. A zero means "not computed yet".
    7. Compute and store. Set cache[i][j] to grid[i][j] plus the smaller of the answers for the cell below and the cell to the right.
    8. Return cache[i][j].

    The solution in Go

    The code uses math.MaxInt, so the file imports math, and it relies on the makeMatrix helper that the lesson supplies.

    func minPathSum(grid [][]int) int {
    cache := makeMatrix(len(grid), len(grid[0]))
    return minSum(grid, cache, 0, 0)
}

func minSum(grid, cache [][]int, i, j int) int {
    if i >= len(grid) || j >= len(grid[0]) {
        return math.MaxInt
    }
    if i == len(grid)-1 && j == len(grid[0])-1 {
        return grid[i][j]
    }
    if cache[i][j] > 0 {
        return cache[i][j]
    }
    cache[i][j] = grid[i][j] + min(minSum(grid, cache, i+1, j), minSum(grid, cache, i, j+1))
    return cache[i][j]
}

    The Go details worth knowing:

    • math.MaxInt as infinity. It is the largest int, 9223372036854775807 on a 64-bit platform. Adding to it would wrap around to a negative number, so the code must never add to it. That never happens: MaxInt is only returned for a cell outside the grid, and a cell has two outside neighbours only at the bottom-right corner, which the base case returns from first. Everywhere else at least one neighbour is a real cell, so min never picks MaxInt and the sum stays small.
    • The order of the checks. The bounds check comes first, because everything after it indexes the grid. The corner check comes before the cache check, so the corner never needs a cache entry.
    • Shared parameter types. grid, cache [][]int declares two parameters of the same type, and i, j int two more.
    • Slices share storage. Passing cache to a function passes a slice header that points at the same rows. Writing cache[i][j] in a deep call changes the table every other call sees. No pointer is needed, because the code modifies elements and never appends.
    • The built-in min. Since Go 1.21 it needs no import and works on any ordered type, including int.
    • The grid is read-only. This solution doesn't modify grid; the next lesson on this problem overwrites it instead.

    Complexity

    Let the grid have m rows and n columns. Time: O(m * n). Each cell computes its value once, with two recursive calls. Every other call reaching the cell returns right after the cache check, and the number of calls is at most twice the number of cells plus the calls that leave the grid.

    Space: O(m * n). The cache has one integer per cell. The recursion goes as deep as the longest chain of moves, m + n - 1 calls, which is small next to the cache.

    Edge cases and common mistakes

    • A single cell. [[5]] returns 5 straight from the base case.
    • One row or one column. [[1,2,3]] returns 6: the only path. In the last row, moving down leaves the grid and returns MaxInt, so min picks the move to the right.
    • Zeros in the grid. The cache uses 0 to mean "not computed", but a cell's answer is 0 when it and everything after it on the best path are 0. Such a cell is recomputed on every visit, and the memoization stops helping. A grid of all zeros is the extreme case: it still returns the right answer, 0, but a 16x16 grid makes about 890 million calls. A cache that records presence separately, for example by filling it with -1, avoids that.
    • Adding to MaxInt. Computing grid[i][j] + minSum(...) before taking the minimum would overflow in the last row and column.
    • Checking the corner before the bounds. Reading grid[i][j] for an out-of-range cell panics with an index out of range error.
    • Greedy choice. Always stepping to the smaller neighbour doesn't work: a cheap cell can lead to an expensive region. In the example grid, greedy goes from 1 to the 1 below it, then prefers the 4 to the 5, finishes through 2 and 1, and ends with 1+1+4+2+1 = 9 instead of 7.

    Testing

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