Minimum Path Sum in Grid in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the first cell of the dp array with the grid's first cell value.

DSA C#

dp[0, 0] = [1];

Drag options to blanks, or click blank then click option'

Adp[0, 0]

B0

C1

Dgrid[0][0]

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing dp[0, 0] with 0 instead of grid[0][0].

Using dp[0, 0] on the right side instead of grid[0][0].

The minimum path sum starting point is the value of the first cell in the grid, so dp[0, 0] should be initialized with grid[0][0].

2fill in blank

medium

Complete the code to fill the first row of the dp array by accumulating sums from the left.

DSA C#

for (int j = 1; j < cols; j++) {
    dp[0, j] = dp[0, j - 1] + [1];
}

Drag options to blanks, or click blank then click option'

Agrid[0][j]

Bdp[0, j]

Cj

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Adding dp[0, j] instead of grid[0][j], causing incorrect accumulation.

Using 0 instead of the grid value.

Each cell in the first row accumulates the sum from the left plus the current grid cell value, so we add grid[0][j].

3fill in blank

hard

Fix the error in the code to fill the dp array for the rest of the grid cells.

DSA C#

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]) + [1];
    }
}

Drag options to blanks, or click blank then click option'

Adp[i][j]

Bgrid[i][j]

Ci + j

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Adding dp[i][j] instead of grid[i][j], causing infinite recursion or wrong values.

Adding 0 instead of the grid value.

To find the minimum path sum at dp[i, j], add the current grid cell value grid[i][j] to the minimum of the top and left dp cells.

4fill in blank

hard

Fill both blanks to initialize the first column of the dp array by accumulating sums from above.

DSA C#

for (int i = 1; i < rows; i++) {
    dp[i, 0] = dp[i - [1], 0] + [2];
}

Drag options to blanks, or click blank then click option'

A1

B0

Cgrid[i][0]

Ddp[i][0]

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of 1 for the row offset.

Adding dp[i][0] instead of grid[i][0].

To fill the first column, add the value from the cell above (dp[i - 1, 0]) plus the current grid cell value grid[i][0].

5fill in blank

hard

Fill all three blanks to complete the method that returns the minimum path sum from top-left to bottom-right.

DSA C#

public int MinPathSum(int[][] grid) {
    int rows = grid.Length;
    int cols = grid[0].Length;
    int[,] dp = new int[rows, cols];
    dp[0, 0] = [1];
    for (int i = 1; i < rows; i++) {
        dp[i, 0] = dp[i - 1, 0] + [2];
    }
    for (int j = 1; j < cols; j++) {
        dp[0, j] = dp[0, j - 1] + [3];
    }
    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];
        }
    }
    return dp[rows - 1, cols - 1];
}

Drag options to blanks, or click blank then click option'

Agrid[0][0]

Bgrid[i][0]

Cgrid[0][j]

Ddp[0, 0]

Attempts:

3 left

💡 Hint

Common Mistakes

Using dp values instead of grid values for initialization.

Mixing up row and column indices.

Initialize dp[0, 0] with grid[0][0]. For the first column, add grid[i][0]. For the first row, add grid[0][j]. This sets up the base cases for the dp array.

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