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, adding the smallest path sum from the top or left neighbor until we reach the bottom-right cell.

Execution Sample

DSA C#

int[,] grid = {
  {1, 3, 1},
  {1, 5, 1},
  {4, 2, 1}
};
int result = MinPathSum(grid);

This code calculates the minimum path sum from the top-left to bottom-right of a 3x3 grid.

Execution Table

Step	Operation	Cell Updated	Value Computed	Grid State
1	Initialize top-left cell	(0,0)	1	[[1, 3, 1], [1, 5, 1], [4, 2, 1]]
2	Update first row cells	(0,1)	1+3=4	[[1, 4, 1], [1, 5, 1], [4, 2, 1]]
3	Update first row cells	(0,2)	4+1=5	[[1, 4, 5], [1, 5, 1], [4, 2, 1]]
4	Update first column cells	(1,0)	1+1=2	[[1, 4, 5], [2, 5, 1], [4, 2, 1]]
5	Update first column cells	(2,0)	2+4=6	[[1, 4, 5], [2, 5, 1], [6, 2, 1]]
6	Update cell (1,1)	(1,1)	min(4,2)+5=7	[[1, 4, 5], [2, 7, 1], [6, 2, 1]]
7	Update cell (1,2)	(1,2)	min(5,7)+1=6	[[1, 4, 5], [2, 7, 6], [6, 2, 1]]
8	Update cell (2,1)	(2,1)	min(7,6)+2=8	[[1, 4, 5], [2, 7, 6], [6, 8, 1]]
9	Update cell (2,2)	(2,2)	min(6,8)+1=7	[[1, 4, 5], [2, 7, 6], [6, 8, 7]]
10	Return result	(2,2)	7	Minimum path sum is 7

💡 Reached bottom-right cell (2,2), minimum path sum computed as 7

Variable Tracker

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

Key Moments - 2 Insights

Why do we 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 first row, top for first column), so their path sums are cumulative sums along that row or column. This is shown in steps 2-5 in the execution_table.

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

Because the problem allows moving only right or down, so the minimum path sum to a cell depends on the smaller path sum of its top or left neighbor plus the current cell's value. This is shown in steps 6-9.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of cell (1,2) after step 7?

A 7

B 5

C 6

D 8

💡 Hint

Check the 'Value Computed' column for step 7 in execution_table.

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

A Step 3

B Step 5

C Step 6

D Step 8

💡 Hint

Look for the operation updating first column cells in execution_table.

If the value at cell (0,1) was 2 instead of 3, how would the value at cell (2,2) change?

A It would decrease

B It would stay the same

C It would increase

D Cannot determine

💡 Hint

Consider how the smaller value at (0,1) affects cumulative sums in execution_table.

Concept Snapshot

Minimum Path Sum in Grid:
- Start at top-left cell
- Move only right or down
- Update each cell with its value plus min(top, left)
- First row and column are cumulative sums
- Result is value at bottom-right cell

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 cell, moving only right or down. We start by initializing the top-left cell with its own value. Then, we update the first row and first column cells by adding their values cumulatively since they have only one direction to come from. For other cells, we update their value by adding the current cell's value to the minimum of the top or left neighbor's path sums. This process continues until we reach the bottom-right cell, which holds the minimum path sum. The example grid shows step-by-step updates, and the final minimum path sum is 7.

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.

easy

A. The maximum number in the grid

B. The path with the largest sum of numbers from top-left to bottom-right

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

D. The path with the smallest sum of numbers from top-left to bottom-right

Solution

1. Step 1: Understand the problem goal

   The problem asks to find a path from the top-left corner to the bottom-right corner of the grid that has the smallest sum of all numbers along the path.

2. Step 2: Clarify path movement

   Movement is only allowed down or right, so the path must be chosen to minimize the total sum.

3. Final Answer:

   The path with the smallest sum of numbers from top-left to bottom-right -> Option D

4. Quick Check:

   Minimum path sum means smallest total sum [OK]

Hint: Look for smallest sum path from top-left to bottom-right [OK]

Common Mistakes:

• Confusing minimum with maximum sum
• Counting number of paths instead of sum
• Ignoring movement restrictions (only down/right)

2. Which of the following C# code snippets correctly initializes a 2D grid for the Minimum Path Sum problem?

easy

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

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

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

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

Solution

1. Step 1: Identify correct 2D array syntax in C#

   In C#, a rectangular 2D array is declared as int[,] grid = new int[rows, columns]; and initialized with nested braces.

2. Step 2: Check each option's syntax

   int[,] grid = new int[3, 3] { {1, 3, 1}, {1, 5, 1}, {4, 2, 1} }; uses int[,] with proper initialization. Options A, C, and D incorrectly mix jagged and rectangular array syntax. int[,] grid = new int[3][3] { {1, 3, 1}, {1, 5, 1}, {4, 2, 1} }; uses invalid syntax for rectangular arrays.

3. Final Answer:

   int[,] grid = new int[3, 3] { {1, 3, 1}, {1, 5, 1}, {4, 2, 1} }; -> Option C

4. Quick Check:

   Rectangular array syntax = int[,] grid = new int[3, 3] { {1, 3, 1}, {1, 5, 1}, {4, 2, 1} }; [OK]

Hint: Use int[,] for 2D rectangular arrays in C# [OK]

Common Mistakes:

• Using jagged array syntax with rectangular arrays
• Mixing [] and [,] incorrectly
• Incorrect initialization braces

3. What is the output of the following C# code?

int[,] grid = { {1, 3, 1}, {1, 5, 1}, {4, 2, 1} };
int rows = grid.GetLength(0);
int cols = grid.GetLength(1);
int[,] dp = new int[rows, cols];
dp[0, 0] = grid[0, 0];
for (int i = 1; i < rows; i++) dp[i, 0] = dp[i - 1, 0] + grid[i, 0];
for (int j = 1; j < cols; j++) dp[0, j] = dp[0, j - 1] + grid[0, j];
for (int i = 1; i < rows; i++) {
  for (int j = 1; j < cols; j++) {
    dp[i, j] = Math.Min(dp[i - 1, j], dp[i, j - 1]) + grid[i, j];
  }
}
Console.WriteLine(dp[rows - 1, cols - 1]);

medium

A. 7

B. 8

C. 10

D. 9

Solution

1. Step 1: Initialize dp array edges

   dp first row: dp[0,0]=1, dp[0,1]=1+3=4, dp[0,2]=4+1=5
   dp first column: dp[1,0]=1+1=2, dp[2,0]=2+4=6

2. Step 2: Fill dp inner 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 A

4. Quick Check:

   Minimum path sum = 7 [OK]

Hint: Use dp to store min sums, check edges first [OK]

Common Mistakes:

• Not initializing first row and column correctly
• Using max instead of min
• Adding wrong grid values

4. The following code tries to compute the minimum path sum but has a bug. What is the bug?

int[,] grid = { {1, 2}, {1, 1} };
int rows = grid.GetLength(0);
int cols = grid.GetLength(1);
int[,] dp = new int[rows, cols];
dp[0, 0] = grid[0, 0];
for (int i = 1; i < rows; i++) dp[i, 0] = dp[i - 1, 0] + grid[i, 0];
for (int j = 1; j < cols; j++) dp[0, j] = dp[0, j - 1] + grid[0, j];
for (int i = 1; i < rows; i++) {
  for (int j = 1; j < cols; j++) {
    dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]) + grid[i, j];
  }
}
Console.WriteLine(dp[rows - 1, cols - 1]);

medium

A. Not initializing dp[0,0]

B. Using Math.Max instead of Math.Min in dp calculation

C. Incorrect loop ranges for i and j

D. Using jagged array syntax for grid

Solution

1. Step 1: Review dp calculation logic

   The problem requires minimum path sum, so dp[i,j] should use Math.Min to choose the smaller previous sum.

2. Step 2: Identify incorrect function usage

   The code uses Math.Max which picks the larger sum, causing incorrect results.

3. Final Answer:

   Using Math.Max instead of Math.Min in dp calculation -> Option B

4. Quick Check:

   Minimum path sum needs Math.Min, not Math.Max [OK]

Hint: Use Math.Min for minimum path sums, not Math.Max [OK]

Common Mistakes:

• Using max instead of min in dp update
• Forgetting to initialize dp edges
• Wrong loop boundaries

5. Given the grid:

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

Write the minimum path sum from top-left to bottom-right if you can only move right or down. What is the sum?

hard

A. 10

B. 9

C. 8

D. 11

Solution

1. Step 1: Initialize dp edges

   First row sums: 1, 4(1+3), 5(4+1), 7(5+2)
   First column sums: 1, 2(1+1), 6(2+4)

2. Step 2: Fill dp inner cells

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

3. Step 3: Find minimum path sum

   The bottom-right cell dp[2,3] = 10 is the minimum path sum.

4. Final Answer:

   10 -> Option A

5. Quick Check:

   Minimum path sum calculated using dp = 10 [OK]

Hint: Calculate dp row and column sums first, then fill inner cells [OK]

Common Mistakes:

• Not updating dp correctly for inner cells
• Mixing up row and column indices
• Forgetting movement restrictions