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.

Practice

1. What does the "Minimum Path Sum in Grid" problem ask you to find?
Given a grid of numbers, find the path from top-left to bottom-right with the smallest sum. Which is true?

easy

A. Find the path with the smallest sum moving only right or down.

B. Find the path with the largest sum moving in any direction.

C. Find the path with the smallest sum moving diagonally only.

D. Find the path with the smallest sum moving left or up.

Solution

1. Step 1: Understand the movement constraints

   The problem allows moving only right or down from each cell in the grid.

2. Step 2: Identify the goal

   The goal is to find the path from the top-left corner to the bottom-right corner with the minimum sum of all numbers on the path.

3. Final Answer:

   Find the path with the smallest sum moving only right or down. -> Option A

4. Quick Check:

   Minimum path sum = smallest sum with right/down moves [OK]

Hint: Remember: only right or down moves allowed [OK]

Common Mistakes:

• Thinking diagonal moves are allowed
• Looking for maximum sum instead of minimum
• Moving left or up which is not allowed

2. Which of the following C code snippets correctly initializes a 2D array named grid with 3 rows and 3 columns filled with zeros?

easy

A. int grid[3][3] = {1};

B. int grid[3][3] = {{1}};

C. int grid[3][3]; memset(grid, 0, sizeof(grid));

D. int grid[3][3] = { {0,0,0}, {0,0,0}, {1,1,1} };

Solution

1. Step 1: Understand array initialization in C

   Initializing a 2D array with zeros can be done by setting all elements to zero using memset after declaration.

2. Step 2: Check each option

   int grid[3][3]; memset(grid, 0, sizeof(grid)); declares the array and then uses memset to set all bytes to zero, correctly initializing all elements to zero.

3. Final Answer:

   int grid[3][3]; memset(grid, 0, sizeof(grid)); -> Option C

4. Quick Check:

   memset sets all elements to zero [OK]

Hint: Use memset for zeroing arrays in C [OK]

Common Mistakes:

• Using {1} only initializes first element
• Confusing single braces with double braces
• Not including string.h for memset

3. What is the output of the following C code that calculates the minimum path sum in a 2x2 grid?

int grid[2][2] = {{1, 3}, {1, 5}};
int dp[2][2];
dp[0][0] = grid[0][0];
for(int i=1; i<2; i++) dp[0][i] = dp[0][i-1] + grid[0][i];
for(int i=1; i<2; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for(int i=1; i<2; i++) {
  for(int j=1; j<2; j++) {
    dp[i][j] = (dp[i-1][j] < dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]) + grid[i][j];
  }
}
printf("%d\n", dp[1][1]);

medium

A. 10

B. 8

C. 9

D. 7

Solution

1. Step 1: Calculate first row and column sums

   dp[0][0] = 1
   dp[0][1] = 1 + 3 = 4
   dp[1][0] = 1 + 1 = 2

2. Step 2: Calculate dp[1][1]

   Minimum of dp[0][1] = 4 and dp[1][0] = 2 is 2
   dp[1][1] = 2 + 5 = 7

3. Final Answer:

   7 -> Option D

4. Quick Check:

   Minimum path sum = 7 [OK]

Hint: Fill dp row and column first, then inner cells [OK]

Common Mistakes:

• Adding max instead of min
• Incorrect dp initialization
• Off-by-one errors in loops

4. The following code attempts to compute the minimum path sum in a 3x3 grid but has a bug. What is the bug?

int grid[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
int dp[3][3];
dp[0][0] = grid[0][0];
for(int i=1; i<3; i++) dp[0][i] = dp[0][i-1] + grid[0][i];
for(int i=1; i<3; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for(int i=1; i<3; i++) {
  for(int j=1; j<3; j++) {
    dp[i][j] = dp[i-1][j] + dp[i][j-1] + grid[i][j];
  }
}

medium

A. The dp update adds both dp[i-1][j] and dp[i][j-1] instead of taking the minimum.

B. The loops start from 1 instead of 0.

C. The dp array is not initialized to zero.

D. The grid values are not accessed correctly.

Solution

1. Step 1: Analyze dp update formula

   The code adds dp[i-1][j] and dp[i][j-1] together plus grid[i][j], which is incorrect.

2. Step 2: Correct dp update

   It should take the minimum of dp[i-1][j] and dp[i][j-1], then add grid[i][j].

3. Final Answer:

   The dp update adds both dp[i-1][j] and dp[i][j-1] instead of taking the minimum. -> Option A

4. Quick Check:

   Use min(dp[i-1][j], dp[i][j-1]) + grid[i][j] [OK]

Hint: Use min, not sum, of top and left dp cells [OK]

Common Mistakes:

• Adding dp values instead of min
• Wrong loop ranges
• Not initializing dp[0][0]

5. Given a 3x3 grid:

int grid[3][3] = {
  {1, 3, 1},
  {1, 5, 1},
  {4, 2, 1}
};

Write the minimum path sum from top-left to bottom-right moving only right or down. What is the minimum sum?

hard

A. 8

B. 7

C. 9

D. 10

Solution

1. Step 1: Calculate dp first row and column

   dp[0][0] = 1
   dp[0][1] = 1+3=4
   dp[0][2] = 4+1=5
   dp[1][0] = 1+1=2
   dp[2][0] = 2+4=6

2. Step 2: Calculate inner dp cells

   dp[1][1] = min(dp[0][1], dp[1][0]) + 5 = min(4,2)+5=7
   dp[1][2] = min(dp[0][2], dp[1][1]) + 1 = min(5,7)+1=6
   dp[2][1] = min(dp[1][1], dp[2][0]) + 2 = min(7,6)+2=8
   dp[2][2] = min(dp[1][2], dp[2][1]) + 1 = min(6,8)+1=7

3. Final Answer:

   7 -> Option B

4. Quick Check:

   Minimum path sum = 7 [OK]

Hint: Fill dp row-wise and column-wise, then inner cells [OK]

Common Mistakes:

• Choosing wrong min between top and left
• Incorrect dp initialization
• Misreading grid values