Start learning free

LESSON 264 OF 347 · BACKTRACKING

Minimum Path Sum in C#: Recursive Backtracking on an int[,] Grid

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

    C# · BACKTRACKING

    Minimum Path Sum in C#, explained

    Problem overview

    The method MinPathSum receives a rectangular grid of non-negative integers as an int[,]. It must find the path from the top-left cell to the bottom-right cell with the smallest total, where every step moves either down or right, and return that total.

    For this 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). The other paths cost more: going down first gives 1 + 1 + 4 + 2 + 1 = 9.

    Approach: ask each cell for its best continuation

    The cheapest path from a cell is the cell's own value plus the cheaper of its two continuations: the best path from the cell below, or the best path from the cell to the right. That sentence is already the algorithm. Write a helper MinSum(grid, i, j) for "the minimum path sum from cell (i, j) to the bottom-right cell", and let it call itself for the two neighbours.

    Two special cases end the recursion:

    • At the bottom-right cell the path is that cell alone, so the answer is its value.
    • Stepping outside the grid is not allowed. The helper reports that with int.MaxValue, a value so large that the minimum never prefers it. This also takes care of the last row and last column, where only one move is available: the move that leaves the grid returns the huge value and loses to the one that stays inside.

    Evaluating the recursion from the bottom-right corner back to the top-left gives these best totals from each cell to the target:

    7 6 3
8 7 2
7 3 1

    The corner is 1. The cell above it holds 1 and can only move down, so its total is 1 + 1 = 2. The middle cell holds 5 and chooses between the cell below (total 3) and the cell to its right (total 2), so its total is 5 + 2 = 7. At the top left, the choice is between 8 (down) and 6 (right), so the answer is 1 + 6 = 7.

    Step by step

    1. Declare MinSum. It is a public method above MinPathSum that takes the int[,] grid and the cell's row i and column j, and returns an int.
    2. Handle leaving the grid. If i >= grid.GetLength(0) or j >= grid.GetLength(1), the move was illegal. Return int.MaxValue.
    3. Handle the target. If i is the last row and j is the last column, return grid[i, j]. This is the base case.
    4. Combine. Return grid[i, j] plus the smaller of MinSum(grid, i + 1, j) (move down) and MinSum(grid, i, j + 1) (move right), using Math.Min.
    5. Start the search. MinPathSum returns MinSum(grid, 0, 0), because every path begins at the top-left cell.

    The solution in C#

    class Solution {

    public int MinSum(int[,] grid, int i, int j) {
        if (i >= grid.GetLength(0) || j >= grid.GetLength(1)) {
            return int.MaxValue;
        }
        if (i == grid.GetLength(0) - 1 && j == grid.GetLength(1) - 1) {
            return grid[i, j];
        }
        return grid[i, j] + Math.Min(MinSum(grid, i + 1, j), MinSum(grid, i, j + 1));
    }

    public int MinPathSum(int[,] grid) {
        return MinSum(grid, 0, 0);
    }
};

    The C# details worth a closer look:

    • Rectangular arrays. int[,] is a single block of rows times columns cells, indexed with a comma: grid[i, j]. It is different from a jagged array int[][], which is an array of separate arrays and is indexed grid[i][j]. Mixing the two styles doesn't compile.
    • Sizes. grid.GetLength(0) is the number of rows and grid.GetLength(1) is the number of columns. grid.Length would be the total number of cells, and grid.Rank is the number of dimensions.
    • Why int.MaxValue is safe here. Adding to it would wrap around silently to a negative number, because int arithmetic is unchecked by default. The code never does that: the only cell where both moves leave the grid is the bottom-right cell, and the second if returns before the sum. Every other cell has at least one move that stays inside, so the minimum is a real total, never the huge value.
    • Trailing semicolon. The ; after the class's closing brace is legal in C# and does nothing.
    • Short-circuit || and &&. The bounds check comes first, so grid[i, j] is only read when i and j are valid.

    Complexity

    Time: exponential. Every cell makes two recursive calls, and different paths reach the same cell again and again. A 3 by 3 grid makes 27 calls; a 4 by 4 grid, 99; an 8 by 8 grid, 18,875; a 12 by 12 grid, 3,997,447. Each extra row and column multiplies the work. The number of distinct cells is only m * n, so almost all of the calls repeat work already done. Caching each cell's answer removes the repetition and reduces the time to O(m * n), which is where the next lessons on this problem go.

    Space: O(m + n). No extra arrays are created. The call stack is as deep as the longest path from the start, which has m + n - 1 cells, and that is the only memory used.

    Edge cases and common mistakes

    • A single cell. {{7}} is both the start and the target, so the answer is 7.
    • A single row or column. For {{1, 2, 3}} the only move is right (the move down leaves the grid), so the answer is 6. A column works the same way.
    • Using -1 or 0 for out-of-bounds. With 0, the minimum would prefer leaving the grid, and the result would be wrong. The out-of-bounds value has to be larger than any real total.
    • Adding to int.MaxValue. Doing something like grid[i, j] + int.MaxValue wraps around to a negative number. Here the structure of the recursion avoids it; if you change the base cases, keep that in mind.
    • Mixing up the dimensions. Row count is GetLength(0), column count is GetLength(1). Swapping them reads past the edge on grids that aren't square and throws an IndexOutOfRangeException.
    • Checking the target before the bounds. Reading grid[i, j] before the bounds test throws on the first step outside the grid.
    • Large grids. The exponential time makes this version suitable only for small grids.

    Testing

    • The grid {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}} gives 7.
    • {{7}} gives 7.
    • {{1, 2, 3}} gives 6, and {{1}, {2}, {3}} gives 6.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free