Minimum Path Sum in Grid in DSA C - Execution Trace

Concept Flow - Minimum Path Sum in Grid

Start at top-left cell (0,0)

↓

At each cell, choose min path sum from top or left

↓

Add current cell value to min of top or left

↓

Move right or down until bottom-right cell

↓

Result is min path sum at bottom-right cell

We start at the top-left cell and move only right or down, accumulating the minimum sum of values along the path until we reach the bottom-right cell.

Execution Sample

DSA C

int minPathSum(int** grid, int rows, int cols) {
  for (int i = 1; i < rows; i++)
    grid[i][0] += grid[i-1][0];
  for (int j = 1; j < cols; j++)
    grid[0][j] += grid[0][j-1];
  for (int i = 1; i < rows; i++) {
    for (int j = 1; j < cols; j++) {
      grid[i][j] += (grid[i-1][j] < grid[i][j-1]) ? grid[i-1][j] : grid[i][j-1];
    }
  }
  return grid[rows-1][cols-1];
}

This code updates the grid in-place to store the minimum path sum to each cell, then returns the bottom-right cell value as the result.

Execution Table

Step	Operation	Cell Updated	Value Added	Grid State	Explanation
1	Initialize first column	(1,0)	grid[0][0] = 1	[[1,3,1],[6,2,1],[1,5,1]]	Add top cell value to current cell in first column
2	Initialize first column	(2,0)	grid[1][0] = 6	[[1,3,1],[6,2,1],[7,5,1]]	Add top cell value to current cell in first column
3	Initialize first row	(0,1)	grid[0][0] = 1	[[1,4,1],[6,2,1],[7,5,1]]	Add left cell value to current cell in first row
4	Initialize first row	(0,2)	grid[0][1] = 4	[[1,4,5],[6,2,1],[7,5,1]]	Add left cell value to current cell in first row
5	Update cell	(1,1)	min(4,6) = 4	[[1,4,5],[6,6,1],[7,5,1]]	Add min of top or left to current cell
6	Update cell	(1,2)	min(5,6) = 5	[[1,4,5],[6,6,6],[7,5,1]]	Add min of top or left to current cell
7	Update cell	(2,1)	min(6,7) = 6	[[1,4,5],[6,6,6],[7,11,1]]	Add min of top or left to current cell
8	Update cell	(2,2)	min(6,11) = 6	[[1,4,5],[6,6,6],[7,11,7]]	Add min of top or left to current cell
9	Return result	(2,2)	7	[[1,4,5],[6,6,6],[7,11,7]]	Minimum path sum is value at bottom-right cell

💡 All cells updated with minimum path sums; bottom-right cell holds final result

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
grid	[[1,3,1],[4,2,1],[1,5,1]]	[[1,3,1],[6,2,1],[1,5,1]]	[[1,3,1],[6,2,1],[7,5,1]]	[[1,4,1],[6,2,1],[7,5,1]]	[[1,4,5],[6,2,1],[7,5,1]]	[[1,4,5],[6,6,1],[7,5,1]]	[[1,4,5],[6,6,6],[7,5,1]]	[[1,4,5],[6,6,6],[7,11,1]]	[[1,4,5],[6,6,6],[7,11,7]]	[[1,4,5],[6,6,6],[7,11,7]]

Key Moments - 3 Insights

Why do we initialize the first row and first column separately before filling the rest?

Because the first row and column can only be reached from one direction (left for row, top for column), so their path sums are cumulative sums along that row or column. This is shown in steps 1-4 in the execution_table.

Why do we add the minimum of the top or left cell to the current cell?

Because the problem allows moving only right or down, so the minimum path to the current cell must come from either the cell above or the cell to the left. This is done in steps 5-8 in the execution_table.

Why is the final answer at the bottom-right cell of the grid?

Because the algorithm accumulates the minimum path sums in-place, so the bottom-right cell contains the minimum sum to reach that cell from the top-left, as shown in step 9.

Visual Quiz - 3 Questions

Look at the execution_table, what is the grid value at cell (1,1) after step 5?

A 6

B 5

C 4

D 7

💡 Hint

Check the 'Grid State' column in row for step 5 in execution_table

At which step does the condition to add min(top, left) to cell (2,2) happen?

A Step 7

B Step 8

C Step 6

D Step 9

💡 Hint

Look for the step updating cell (2,2) in execution_table

If the initial value at grid[0][0] was 2 instead of 1, how would the final minimum path sum change?

A It would increase by 1

B It would stay the same

C It would decrease by 1

D It would double

💡 Hint

Check variable_tracker for how grid[0][0] affects all subsequent sums

Concept Snapshot

Minimum Path Sum in Grid:
- Start at top-left cell
- Initialize first row and column by cumulative sums
- For each other cell, add min(top, left) cell value
- Result is value at bottom-right cell
- Only moves allowed: right or down

Full Transcript

The Minimum Path Sum in Grid problem finds the smallest sum of numbers along a path from the top-left to the bottom-right of a grid, moving only right or down. The approach updates the grid in-place: first, it initializes the first row and column by adding values cumulatively since those cells can only be reached from one direction. Then, for each other cell, it adds the minimum of the top or left neighbor's path sums to the current cell's value. This way, each cell stores the minimum path sum to reach it. Finally, the bottom-right cell contains the minimum path sum for the entire grid. The execution table shows each step updating the grid, and the variable tracker follows the grid's state after each update. Key moments clarify why initialization is separate and why the minimum of top and left is chosen. The visual quiz tests understanding of these steps and the effect of changing initial values.

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