Start learning free

LESSON 269 OF 338 · MEMOIZATION

Minimum Path Sum III in Go: Bottom-Up DP Using the Grid

Practice O(n2) - DP 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.
STEP 1 OF 5
    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 moves only down or right. The function returns the smallest sum of the numbers along a path, including both end cells.

    For [[1,3,1],[1,5,1],[4,2,1]] the answer is 7, from the path 1, 3, 1, 1, 1.

    Approach: build the answers from the top-left corner

    Let best(i, j) be the cheapest sum of a path from the top-left cell to (i, j). A path can enter a cell only from above or from the left, so for a cell away from the edges:

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

    The cells on the first row have only a left neighbour, and the cells in the first column have only an upper neighbour. The corner is its own answer. Filling the cells in an order where both neighbours are always done first needs no recursion at all: first row, first column, then the rest row by row.

    The earlier version of this problem asks the question top-down, from the start toward the end, and caches the answers. This version asks it bottom-up and in the opposite direction, from the start to each cell. Both cost O(m * n) time. The difference is memory and call overhead: no recursion, no cache table, because the grid itself can hold the answers.

    That last point is a deliberate trade. Once best(i, j) is known, the original grid[i][j] is never needed again, since later cells read only the finished values of their neighbours. So each cell can be overwritten in place.

    Step by step

    1. Read the sizes once. n, m := len(grid), len(grid[0]) gives the number of rows and columns in a single declaration.
    2. Fill the first row. For j from 1 to m - 1, add the left neighbour. Each cell becomes the running total along the row. Starting at 1 guarantees that the left neighbour exists, and the corner stays as it is.
    3. Fill the first column. For i from 1 to n - 1, add the cell above. The same running total goes down the column.
    4. Fill the interior. Two nested loops from 1 add the smaller of the upper and left neighbours. Going row by row, left to right, means both neighbours are already final when a cell is computed.
    5. Return the bottom-right cell, grid[n-1][m-1].

    The solution in Go

    func minPathSum(grid [][]int) int {
    n, m := len(grid), len(grid[0])
    for j := 1; j < m; j++ {
        grid[0][j] += grid[0][j-1]
    }
    for i := 1; i < n; i++ {
        grid[i][0] += grid[i-1][0]
    }
    for i := 1; i < n; i++ {
        for j := 1; j < m; j++ {
            grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        }
    }
    return grid[n-1][m-1]
}

    On the example, the first row becomes [1, 4, 5] and the first column becomes [1, 2, 6]. The center cell then takes 5 + min(4, 2) = 7, the middle right cell takes 1 + min(5, 7) = 6, the bottom middle takes 2 + min(7, 6) = 8, and the last cell takes 1 + min(6, 8) = 7. The grid ends as [[1 4 5] [2 7 6] [6 8 7]] and the function returns 7.

    The Go details worth knowing:

    • Multiple assignment. n, m := len(grid), len(grid[0]) declares both variables at once. The names are the other way round from the usual convention of m rows and n columns, so keep track of which is which: here n counts rows and m counts columns.
    • Compound assignment on elements. grid[0][j] += grid[0][j-1] reads and writes the same cell. The right side uses the neighbour that was updated in the previous iteration, which is what turns the row into a running total.
    • The built-in min. Since Go 1.21 it is part of the language, so there is no import and no helper function.
    • The caller's grid changes. A [][]int is a slice of slices, and the rows are shared with the caller. After the call the caller's grid holds the totals, not the original numbers. Copy the rows first if the input is still needed.

    Complexity

    Let the grid have n rows and m columns. Time: O(n * m). The first row and column take m - 1 and n - 1 steps, and the interior loops visit each of the remaining (n - 1) * (m - 1) cells once with constant work.

    Space: O(1) extra. The answers are stored in the input grid, and the function uses a handful of integers. The earlier version of this problem needs an extra table of the same size plus the recursion stack.

    Edge cases and common mistakes

    • One cell. [[5]] skips all three loops and returns 5.
    • One row or one column. [[1,2,3]] returns 6 and [[1],[2],[3]] returns 6. The interior loops don't run, and the edge loops do all the work.
    • An empty grid. len(grid[0]) panics on a grid with no rows. The lesson's grids always have at least one cell.
    • Starting a loop at 0. The first-row loop would read grid[0][-1] and panic with an index out of range error.
    • Filling the interior before the edges. The cells on the first row and column wouldn't be final yet, and the interior would read partial sums.
    • Forgetting that the grid is modified. Calling minPathSum twice on the same grid gives a wrong second answer, because the second call adds sums to sums. For the example the second call returns 23 instead of 7.
    • Mixing up rows and columns. With n rows and m columns the answer sits at grid[n-1][m-1]; swapping the two indexes panics on non-square grids.

    Testing

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