Minimum Path Sum in Grid in DSA C

Mental Model

Find the smallest total by moving only right or down from the top-left to the bottom-right of a grid.

Analogy: Imagine walking through a city grid where each block has a cost to cross. You want to find the cheapest path from your home (top-left) to your friend's house (bottom-right) by only moving east or south.

Start:
[0,0] -> [0,1] -> [0,2]
  ↓       ↓       ↓
[1,0] -> [1,1] -> [1,2]
  ↓       ↓       ↓
[2,0] -> [2,1] -> [2,2]

You can only move -> or ↓ from each cell.

Dry Run Walkthrough

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]

Goal: Find the minimum sum path from top-left to bottom-right moving only right or down.

Step 1: Initialize first row by accumulating sums moving right

[1, 4, 5]
[1, 5, 1]
[4, 2, 1]

Why: We can only move right in the first row, so sums accumulate from left to right.

Step 2: Initialize first column by accumulating sums moving down

[1, 4, 5]
[2, 5, 1]
[6, 2, 1]

Why: We can only move down in the first column, so sums accumulate from top to bottom.

Step 3: Calculate minimum path sums for cell (1,1) by choosing min from top or left

[1, 4, 5]
[2, 7, 1]
[6, 2, 1]

Why: At (1,1), choose min(4,2) + 5 = 7 to get minimum sum path.

Step 4: Calculate minimum path sums for cell (1,2)

[1, 4, 5]
[2, 7, 6]
[6, 2, 1]

Why: At (1,2), choose min(5,7) + 1 = 5 + 1 = 6 for minimum sum.

Step 5: Calculate minimum path sums for cell (2,1)

[1, 4, 5]
[2, 7, 6]
[6, 8, 1]

Why: At (2,1), choose min(7,6) + 2 = 6 + 2 = 8 for minimum sum.

Step 6: Calculate minimum path sums for cell (2,2)

[1, 4, 5]
[2, 7, 6]
[6, 8, 7]

Why: At (2,2), choose min(6,8) + 1 = 6 + 1 = 7 for minimum sum.

Result:

Final grid with minimum path sums:
[1, 4, 5]
[2, 7, 6]
[6, 8, 7]
Minimum path sum = 7

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

int min(int a, int b) {
    return (a < b) ? a : b;
}

int minPathSum(int** grid, int gridSize, int* gridColSize) {
    int rows = gridSize;
    int cols = gridColSize[0];

    // Initialize first row
    for (int c = 1; c < cols; c++) {
        grid[0][c] += grid[0][c - 1];
    }

    // Initialize first column
    for (int r = 1; r < rows; r++) {
        grid[r][0] += grid[r - 1][0];
    }

    // Fill the rest of the grid
    for (int r = 1; r < rows; r++) {
        for (int c = 1; c < cols; c++) {
            grid[r][c] += min(grid[r - 1][c], grid[r][c - 1]);
        }
    }

    return grid[rows - 1][cols - 1];
}

int main() {
    int gridData[3][3] = {
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1}
    };

    int* grid[3];
    for (int i = 0; i < 3; i++) {
        grid[i] = gridData[i];
    }

    int gridColSize[3] = {3, 3, 3};

    int result = minPathSum(grid, 3, gridColSize);
    printf("Minimum path sum = %d\n", result);
    return 0;
}

for (int c = 1; c < cols; c++) { grid[0][c] += grid[0][c - 1]; }

Accumulate sums along the first row since only right moves are possible.

for (int r = 1; r < rows; r++) { grid[r][0] += grid[r - 1][0]; }

Accumulate sums along the first column since only down moves are possible.

for (int r = 1; r < rows; r++) { for (int c = 1; c < cols; c++) { grid[r][c] += min(grid[r - 1][c], grid[r][c - 1]); } }

For each cell, add the minimum of the top or left cell to find the minimum path sum.

return grid[rows - 1][cols - 1];

Return the bottom-right cell which contains the minimum path sum.

Output

Minimum path sum = 7

Complexity Analysis

Time: O(m*n) because we visit each cell once to compute the minimum path sum.

Space: O(1) because we update the grid in place without extra space.

vs Alternative: Compared to recursive solutions without memoization which are exponential, this dynamic programming approach is efficient and uses constant extra space.

Edge Cases

Grid with only one cell

Returns the value of the single cell as the minimum path sum.

DSA C

return grid[rows - 1][cols - 1];

Grid with one row

Accumulates sums along the row correctly since only right moves are possible.

DSA C

for (int c = 1; c < cols; c++) { grid[0][c] += grid[0][c - 1]; }

Grid with one column

Accumulates sums along the column correctly since only down moves are possible.

DSA C

for (int r = 1; r < rows; r++) { grid[r][0] += grid[r - 1][0]; }

When to Use This Pattern

When you need to find a path with minimum cost in a grid moving only right or down, use dynamic programming to build solutions from smaller subproblems.

Common Mistakes

Mistake: Not initializing the first row and first column sums before filling the rest of the grid.
Fix: Explicitly accumulate sums for the first row and first column before the main loop.

Mistake: Using max instead of min when choosing between top and left cells.
Fix: Use the minimum of the two to ensure the smallest path sum.

Summary

Calculates the smallest sum path from the top-left to bottom-right of a grid moving only right or down.

Use when you want to find the cheapest route through a grid with movement restrictions.

Build the solution by accumulating minimum sums row-wise and column-wise, then filling the grid using the minimum of top and left neighbors.