Start learning free

LESSON 274 OF 347 · MEMOIZATION

Minimum Path Sum in C#: Iterative DP on an int[,] 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

    C# · MEMOIZATION

    Minimum Path Sum in C#, explained

    Problem overview

    You get a grid of non-negative integers with m rows and n columns. Starting at the top-left cell, you move only down or right until you reach the bottom-right cell. MinPathSum returns the smallest possible sum of the numbers along such a path, counting both end cells.

    For the grid below, the answer is 7, from the path 1, 3, 1, 1, 1:

    1 3 1
1 5 1
4 2 1

    Approach: build the answer from the top-left corner

    Instead of asking "what is the best path from here to the end?", this solution asks "what is the best path from the start to here?". Let best(i, j) be the minimum sum of a path from the top-left cell to (i, j). Because moves go only down or right, a path reaches (i, j) from the cell above or from the cell to the left, so:

    • best(0, 0) is the cell's own value.
    • On the first row, only the left neighbor exists: best(0, j) = grid[0, j] + best(0, j - 1).
    • In the first column, only the cell above exists: best(i, 0) = grid[i, 0] + best(i - 1, 0).
    • Everywhere else, take the better of the two: best(i, j) = grid[i, j] + min(best(i - 1, j), best(i, j - 1)).

    Filling the cells row by row, left to right, guarantees that both neighbors are final when a cell is computed. No recursion is needed. To save memory the solution stores each best value in the input grid itself, overwriting the original number. That makes the extra space O(1), at the price of changing the caller's array.

    On the example, the first row becomes 1 4 5 (a running total) and the first column becomes 1 2 6. The inner four cells then fill in as follows:

    • (1, 1): 5 + min(4, 2) = 7
    • (1, 2): 1 + min(5, 7) = 6
    • (2, 1): 2 + min(7, 6) = 8
    • (2, 2): 1 + min(6, 8) = 7

    The bottom-right cell holds 7, which is the answer.

    Step by step

    1. Read the dimensions once: n is grid.GetLength(0), the number of rows, and m is grid.GetLength(1), the number of columns. Both can be declared in one int statement.
    2. Fill the first row. Loop j from 1 to m - 1 and add grid[0, j - 1] to grid[0, j]. Cell (0, 0) stays as it is, and starting at 1 guarantees that the left neighbor exists. Each step uses the already updated value on its left, so the row turns into running totals.
    3. Fill the first column the same way: loop i from 1 to n - 1 and add grid[i - 1, 0] to grid[i, 0].
    4. Fill the rest. With nested loops over i from 1 and j from 1, add Math.Min(grid[i - 1, j], grid[i, j - 1]) to grid[i, j].
    5. Return grid[n - 1, m - 1], the best sum for the bottom-right cell.

    The solution in C#

    class Solution {

    public int MinPathSum(int[,] grid) {
        int n = grid.GetLength(0), m = grid.GetLength(1);

        for (int j = 1; j < m; ++j) {
            grid[0, j] += grid[0, j - 1];
        }

        for (int i = 1; i < n; ++i) {
            grid[i, 0] += grid[i - 1, 0];
        }

        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < m; ++j) {
                grid[i, j] += Math.Min(grid[i - 1, j], grid[i, j - 1]);
            }
        }

        return grid[n - 1, m - 1];
    }
}

    C# details worth knowing

    • Rectangular arrays. int[,] is indexed with a comma, grid[i, j]. A jagged array int[][] would be indexed as grid[i][j], and the two types are not interchangeable.
    • Rows and columns. grid.Length is the total number of cells, so use GetLength(0) for rows and GetLength(1) for columns.
    • Arrays are passed by reference. The method changes the caller's grid, and after the call it holds running totals instead of the original numbers. If the caller still needs them, copy the grid first with (int[,])grid.Clone().
    • Compound assignment. grid[i, j] += x reads, adds and writes the same cell.

    Complexity

    Every cell is visited a constant number of times, so the time is O(n * m). The table lives inside the input, so no extra array is allocated and the extra space is O(1). The memoized recursive version uses O(n * m) extra space for its cache and for the call stack, and this one avoids both.

    If you prefer not to modify the input, allocate a second int[,] of the same size and write the totals there. The loops stay the same, but they read the original numbers from grid and the totals from the new array. The extra space then becomes O(n * m), like the memoized version. Overwriting the grid is a trade: less memory in exchange for losing the original values, which is fine whenever the caller never uses the grid again.

    Edge cases and common mistakes

    • A single cell. All three loops run zero times, and the method returns grid[0, 0].
    • A single row or column. Only one of the first two loops does any work, and the answer is the sum of all the cells. For [1, 2, 3] as a one-row grid it is 6.
    • Starting the loops at 0. Then grid[0, j - 1] would be grid[0, -1], which throws IndexOutOfRangeException.
    • Swapping the dimensions. Using GetLength(1) for rows gives wrong results or throws IndexOutOfRangeException on grids that are not square.
    • Filling inner cells first. A cell reads its upper and left neighbors, so they must already hold their final values. Row-by-row order from the top left guarantees that, once the first row and column are done.

    Testing

    Results from running the solution:

    • The 3 x 3 grid above returns 7.
    • A one-cell grid { { 5 } } returns 5.
    • A column { { 1 }, { 2 }, { 3 } } returns 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