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, calculate min path sum

↓

Move right or down

↓

Update cell with min sum

↓

Repeat until bottom-right cell

↓

Result is value at bottom-right cell

We start from the top-left cell and move only right or down, updating each cell with the minimum path sum to reach it, until we reach the bottom-right cell.

Execution Sample

DSA C++

int minPathSum(vector<vector<int>>& grid) {
  int m = grid.size(), n = grid[0].size();
  for (int i = 1; i < m; i++) grid[i][0] += grid[i-1][0];
  for (int j = 1; j < n; j++) grid[0][j] += grid[0][j-1];
  for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
      grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
    }
  }
  return grid[m-1][n-1];
}

This code updates the grid in-place to store the minimum path sum to each cell, moving only right or down.

Execution Table

Step	Operation	Cell Updated	Value Added	Grid State (3x3 example)
1	Initialize first column	(1,0)	grid[1][0] += grid[0][0] = 3 + 1	[[1,3,1],[4,1,5],[1,2,1]]
2	Initialize first column	(2,0)	grid[2][0] += grid[1][0] = 1 + 4	[[1,3,1],[4,1,5],[5,2,1]]
3	Initialize first row	(0,1)	grid[0][1] += grid[0][0] = 3 + 1	[[1,4,1],[4,1,5],[5,2,1]]
4	Initialize first row	(0,2)	grid[0][2] += grid[0][1] = 1 + 4	[[1,4,5],[4,1,5],[5,2,1]]
5	Update cell	(1,1)	grid[1][1] += min(grid[0][1], grid[1][0]) = 1 + min(4,4) = 5	[[1,4,5],[4,5,5],[5,2,1]]
6	Update cell	(1,2)	grid[1][2] += min(grid[0][2], grid[1][1]) = 5 + min(5,5) = 10	[[1,4,5],[4,5,10],[5,2,1]]
7	Update cell	(2,1)	grid[2][1] += min(grid[1][1], grid[2][0]) = 2 + min(5,5) = 7	[[1,4,5],[4,5,10],[5,7,1]]
8	Update cell	(2,2)	grid[2][2] += min(grid[1][2], grid[2][1]) = 1 + min(10,7) = 8	[[1,4,5],[4,5,10],[5,7,8]]
9	Return result	bottom-right (2,2)	grid[2][2] = 8	Final minimum path sum = 8

💡 Reached bottom-right cell; minimum path sum computed.

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],[3,1,5],[1,2,1]]	[[1,3,1],[4,1,5],[1,2,1]]	[[1,3,1],[4,1,5],[5,2,1]]	[[1,4,1],[4,1,5],[5,2,1]]	[[1,4,5],[4,1,5],[5,2,1]]	[[1,4,5],[4,5,5],[5,2,1]]	[[1,4,5],[4,5,10],[5,2,1]]	[[1,4,5],[4,5,10],[5,7,1]]	[[1,4,5],[4,5,10],[5,7,8]]	[[1,4,5],[4,5,10],[5,7,8]]

Key Moments - 3 Insights

Why do we first update the first row and first column separately before the rest of the grid?

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

Why do we add the minimum of the top and left cells when updating other cells?

Because from each cell, we can only come from the top or left, so the minimum path sum to the current cell is its own value plus the smaller of the two possible previous sums. See execution_table steps 5-8.

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

Because the problem asks for the minimum path sum from top-left to bottom-right, and after updating all cells, the bottom-right cell holds the total minimum sum. This is confirmed in execution_table step 9.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the updated value of cell (1,1)?

A 5

B 4

C 1

D 10

💡 Hint

Refer to execution_table row with Step 5 showing cell (1,1) updated to 5.

At which step does the value of cell (2,2) get updated?

A Step 7

B Step 8

C Step 6

D Step 9

💡 Hint

Check execution_table row where cell (2,2) is updated with value 8.

If the initial grid's first row was [1, 2, 3] instead of [1, 3, 1], how would the value at cell (0,2) after initialization change?

A It would be 6

B It would be 5

C It would remain 5

D It would be 4

💡 Hint

Refer to variable_tracker and execution_table steps 3 and 4 for first row cumulative sums.

Concept Snapshot

Minimum Path Sum in Grid:
- Start at top-left cell.
- Update first row and column with cumulative sums.
- For other cells, add cell value to min(top, left) cell sums.
- Result is bottom-right cell value.
- Moves allowed: right or down only.

Full Transcript

The Minimum Path Sum in Grid problem involves finding the smallest sum of numbers along a path from the top-left to the bottom-right of a grid, moving only right or down. We start by updating the first row and first column with cumulative sums because they have only one path to reach each cell. Then, for each other cell, we add its value to the minimum of the sums from the cell above or to the left. This process continues until we reach the bottom-right cell, which holds the minimum path sum. The provided code updates the grid in-place to store these sums. The execution table traces each update step, showing how the grid changes. Key moments clarify why the first row and column are handled separately and why the minimum of top and left cells is used. The visual quiz tests understanding of these updates and their timing.

Practice

1. What does the "Minimum Path Sum in Grid" problem ask you to find?

easy

A. The largest sum of numbers along any path in the grid.

B. The shortest path length from top-left to bottom-right.

C. The number of paths from top-left to bottom-right.

D. The smallest sum of numbers along a path from top-left to bottom-right, moving only right or down.

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum sum of values collected when moving from the top-left corner to the bottom-right corner of a grid, moving only right or down.

2. Step 2: Clarify movement constraints

   Only moves to the right or down are allowed, so the path is restricted and the sum depends on chosen cells.

3. Final Answer:

   The smallest sum of numbers along a path from top-left to bottom-right, moving only right or down. -> Option D

4. Quick Check:

   Minimum path sum = smallest sum path [OK]

Hint: Focus on sum along right/down moves only [OK]

Common Mistakes:

• Thinking diagonal moves are allowed
• Looking for maximum sum instead of minimum
• Counting number of paths instead of sum

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

easy

A. std::vector grid(3, std::vector<int>(4, 0));

B. std::vector<int> grid(3, std::vector<int>(4, 0));

C. std::vector grid(4, std::vector<int>(3, 0));

D. std::vector grid(3, 4, 0);

Solution

1. Step 1: Understand 2D vector initialization syntax

   To create a 2D vector with 3 rows and 4 columns filled with zeros, we use vector of vectors: outer vector size 3, inner vector size 4, each element 0.

2. Step 2: Check each option

   std::vector grid(3, std::vector<int>(4, 0)); correctly uses std::vector grid(3, std::vector<int>(4, 0)); which means 3 rows, each row is a vector of 4 zeros.

3. Final Answer:

   std::vector grid(3, std::vector<int>(4, 0)); -> Option A

4. Quick Check:

   Correct 2D vector init = std::vector grid(3, std::vector<int>(4, 0)); [OK]

Hint: Use vector of vectors with inner vector size and default value [OK]

Common Mistakes:

• Using wrong vector type for 2D
• Swapping rows and columns sizes
• Trying to pass three arguments to vector constructor

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

std::vector grid = {{1, 3}, {1, 5}};
int m = grid.size();
int n = grid[0].size();
for (int i = 1; i < m; i++) grid[i][0] += grid[i-1][0];
for (int j = 1; j < n; j++) grid[0][j] += grid[0][j-1];
for (int i = 1; i < m; i++) {
  for (int j = 1; j < n; j++) {
    grid[i][j] += std::min(grid[i-1][j], grid[i][j-1]);
  }
}
std::cout << grid[m-1][n-1] << std::endl;

medium

A. 7

B. 8

C. 9

D. 10

Solution

1. Step 1: Calculate first column cumulative sums

   grid[1][0] = grid[1][0] + grid[0][0] = 1 + 1 = 2

2. Step 2: Calculate first row cumulative sums

   grid[0][1] = grid[0][1] + grid[0][0] = 3 + 1 = 4

3. Step 3: Calculate inner cell minimum path sums

   grid[1][1] = grid[1][1] + min(grid[0][1], grid[1][0]) = 5 + min(4, 2) = 5 + 2 = 7

4. Final Answer:

   7 -> Option A

5. Quick Check:

   Minimum path sum = 7 [OK]

Hint: Update first row and column cumulatively, then inner cells [OK]

Common Mistakes:

• Not updating first row and column before inner cells
• Adding max instead of min
• Mixing indices i and j

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

std::vector grid = {{1, 2, 3}, {4, 5, 6}};
int m = grid.size();
int n = grid[0].size();
for (int i = 1; i < m; i++) grid[i][0] += grid[i-1][0];
for (int j = 1; j < n; j++) grid[0][j] += grid[0][j-1];
for (int i = 1; i < m; i++) {
  for (int j = 1; j < n; j++) {
    grid[i][j] += std::max(grid[i-1][j], grid[i][j-1]);
  }
}
std::cout << grid[m-1][n-1] << std::endl;

medium

A. Wrong loop ranges for i and j

B. Not initializing first row and column

C. Using std::max instead of std::min in inner loop

D. Incorrect grid initialization syntax

Solution

1. Step 1: Check the inner loop operation

   The code uses std::max to update grid[i][j], but the problem requires minimum path sum, so std::min should be used.

2. Step 2: Verify other parts

   First row and column are correctly initialized, loops have correct ranges, and grid initialization is valid.

3. Final Answer:

   Using std::max instead of std::min in inner loop -> Option C

4. Quick Check:

   Use min for minimum path sum [OK]

Hint: Use min, not max, when updating path sums [OK]

Common Mistakes:

• Confusing max and min functions
• Skipping first row/column initialization
• Off-by-one errors in loops

5. Given the grid below, what is the minimum path sum from top-left to bottom-right?

grid = {
  {1, 3, 1, 2},
  {1, 5, 1, 1},
  {4, 2, 1, 3}
};

You can only move right or down. Calculate the minimum sum.

hard

A. 8

B. 10

C. 9

D. 11

Solution

1. Step 1: Compute first row and first column cumulative sums

   First row: [1, 4, 5, 7] (1, 1+3=4, 4+1=5, 5+2=7) First column: [1, 2, 6] (1, 1+1=2, 2+4=6)

2. Step 2: Calculate inner cells minimum path sums

   Row 1, col 1: 5 + min(4,2) = 5 + 2 = 7 Row 1, col 2: 1 + min(5,7) = 1 + 5 = 6 Row 1, col 3: 1 + min(7,6) = 1 + 6 = 7 Row 2, col 1: 2 + min(7,6) = 2 + 6 = 8 Row 2, col 2: 1 + min(6,8) = 1 + 6 = 7 Row 2, col 3: 3 + min(7,7) = 3 + 7 = 10

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Minimum path sum = 10 [OK]

Hint: Fill first row/column, then inner cells with min sums [OK]

Common Mistakes:

• Adding max instead of min
• Incorrect cumulative sums for first row/column
• Misindexing grid cells