Start learning free

LESSON 259 OF 338 · BACKTRACKING

Minimum Path Sum in Go: Recursive Backtracking

Practice O(2n) 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:

Your algorithm should run in O(n * m) time and use O(n * m) extra space.

STEP 1 OF 5
    Ctrl + Enter to check

    GO · BACKTRACKING

    Minimum Path Sum in Go, explained

    Problem overview

    The function minPathSum(grid) receives a rectangular grid of non-negative integers as a [][]int. A path starts in the top-left cell and ends in the bottom-right cell, moving only down or right. The sum of a path is the total of all the cells it visits, both ends included. The function returns the smallest possible sum.

    For this grid the answer is 7:

    [1 3 1]
[1 5 1]
[4 2 1]

    The path 1, 3, 1, 1, 1 goes right, right, down, down and adds up to 7.

    Approach: the best path from a cell

    Let minSum(grid, i, j) be the smallest path sum from cell (i, j) to the bottom-right cell. From any cell there are only two moves, down to (i + 1, j) or right to (i, j + 1). The best path from a cell is its own value plus the better of the two continuations. The answer to the problem is minSum(grid, 0, 0).

    The recursion needs two base cases. At the bottom-right cell the path is that single cell, so the sum is its value. Moves that fall off the grid are not paths at all. Instead of special handling, such a move returns math.MaxInt, the largest int, so the minimum of the two continuations never selects it.

    This version is a backtracking solution: it follows every route and keeps the cheapest. The same cell is reached over and over by different routes, so the number of calls grows quickly. For a 3 by 3 grid it makes 27 calls, for 5 by 5 it makes 363, for 10 by 10 it makes 272,271 and for 15 by 15 it makes 230,001,839. A later lesson on this problem saves each cell's answer and reduces the work to one computation per cell, which is O(n * m).

    Step by step

    1. Declare the helper minSum above minPathSum. It takes grid [][]int and the indices i, j int, which share one type name, and returns an int.
    2. Off the grid. If i >= len(grid) or j >= len(grid[0]), return math.MaxInt.
    3. Bottom-right cell. If i equals len(grid)-1 and j equals len(grid[0])-1, return grid[i][j]. This stops the recursion.
    4. Recurse. Return grid[i][j] plus the smaller of minSum(grid, i+1, j) and minSum(grid, i, j+1).
    5. Start at the corner. minPathSum returns minSum(grid, 0, 0).

    The solution in Go

    func minSum(grid [][]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]
    }
    return grid[i][j] + min(minSum(grid, i+1, j), minSum(grid, i, j+1))
}

func minPathSum(grid [][]int) int {
    return minSum(grid, 0, 0)
}

    Go details worth knowing:

    • The import. math.MaxInt comes from the math package, which a complete program must import. It equals 9223372036854775807 on a 64-bit build.
    • Why MaxInt doesn't overflow. Adding to the largest int would wrap to a huge negative number, since Go integers overflow silently. That never happens here. A call only sees MaxInt from a neighbour that fell off the grid, and the other neighbour is on the grid except at the bottom-right cell, which returns before the addition. So the minimum always picks a real sum, and MaxInt is never added to anything.
    • Built-in min. Since Go 1.21, min works on ordered types without an import.
    • Order of the checks. The bounds test must come first. For a cell outside the grid, the final return would index grid[i][j] outside the grid and panic.
    • len(grid[0]) is the width. A [][]int is a slice of row slices, so the number of columns is the length of any row, here the first. This assumes that grid has at least one row.

    Complexity

    Time: exponential in the grid size. Every cell inside the grid except the bottom-right one makes two calls, and the number of routes to a cell grows combinatorially, so the same subproblems are solved many times.

    Space: O(m + n) for the call stack, where m and n are the number of rows and columns. Every call moves one step down or right, so a route has at most m + n - 1 cells, and nothing else is allocated.

    Edge cases and common mistakes

    • One cell. [[5]] is the bottom-right cell already, so the answer is 5.
    • One row or one column. [[1, 2, 3]] and a column [[1], [2], [3]] both give 6, because there is only one path. The off-grid moves return MaxInt and the minimum ignores them.
    • Counting the start and end. Both corner cells are part of the path. A recursion that returns 0 at the end would miss the last cell's value.
    • Greedy choices. Always stepping to the smaller neighbour can fail, because a small cell can lead into expensive ones. The recursion compares whole paths, not single steps.
    • Using 0 for off-grid moves. That would make a move off the grid look free and the minimum would pick it. A large value is needed.
    • Grids that are too large. The call count grows so fast that a 15 by 15 grid already takes hundreds of millions of calls.

    Testing

    The grid [[1, 3, 1], [1, 5, 1], [4, 2, 1]] gives 7. [[5]] gives 5. [[1, 2, 3]] gives 6.

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