Minimum Path Sum in Grid in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Path Sum Calculation

What is the output of the following C# code that calculates the minimum path sum in a 3x3 grid?

DSA C#

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

int m = grid.Length;
int n = grid[0].Length;
int[,] dp = new int[m, n];

dp[0, 0] = grid[0][0];
for (int i = 1; i < m; i++)
    dp[i, 0] = dp[i - 1, 0] + grid[i][0];
for (int j = 1; j < n; j++)
    dp[0, j] = dp[0, j - 1] + grid[0][j];

for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        dp[i, j] = Math.Min(dp[i - 1, j], dp[i, j - 1]) + grid[i][j];
    }
}

Console.WriteLine(dp[m - 1, n - 1]);

A 10

B 8

C 9

D 7

💡 Hint

Trace the path with the smallest sum from top-left to bottom-right, moving only right or down.

The minimum path sum is calculated by dynamic programming. The path is 1 → 3 → 1 → 1 → 1, summing to 7.

🧠 Conceptual

intermediate

Understanding Movement Constraints in Minimum Path Sum

In the minimum path sum problem on a grid, which movement directions are allowed to find the path?

A Moves can be in any of the four directions

B Only left and up moves are allowed

C Only right and down moves are allowed

D Only diagonal moves are allowed

💡 Hint

Think about how the problem restricts movement to avoid cycles.

The problem restricts movement to only right or down to ensure a unique path and avoid cycles.

🔧 Debug

advanced

Identify the Error in Minimum Path Sum Code

What error will the following C# code produce when calculating minimum path sum?

DSA C#

int[][] grid = new int[][] {
    new int[] {1, 2},
    new int[] {1, 1}
};

int m = grid.Length;
int n = grid[0].Length;
int[,] dp = new int[m, n];

dp[0, 0] = grid[0][0];
for (int i = 1; i < m; i++)
    dp[i, 0] = dp[i - 1, 0] + grid[i][0];
for (int j = 1; j < n; j++)
    dp[0, j] = dp[0, j - 1] + grid[0][j];

A IndexOutOfRangeException

B NullReferenceException

C No error, outputs 3

D Compile-time error

💡 Hint

Check the loop boundary conditions carefully.

The for loop uses i <= m which causes index i to go out of bounds since valid indices are 0 to m-1.

🚀 Application

advanced

Minimum Path Sum in a Larger Grid

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

DSA C#

int[][] grid = new int[][] {
    new int[] {5, 9, 6},
    new int[] {11, 5, 2},
    new int[] {4, 7, 1}
};

// Calculate minimum path sum using the standard DP approach

A 18

B 22

C 20

D 21

💡 Hint

Add the smallest sums step by step from top-left to bottom-right.

The minimum path sum is 22, following the path 5 → 9 → 5 → 2 → 1.

❓ Predict Output

expert

Output of Minimum Path Sum with Negative Values

What is the output of this C# code that calculates minimum path sum in a grid containing negative values?

DSA C#

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

int m = grid.Length;
int n = grid[0].Length;
int[,] dp = new int[m, n];

dp[0, 0] = grid[0][0];
for (int i = 1; i < m; i++)
    dp[i, 0] = dp[i - 1, 0] + grid[i][0];
for (int j = 1; j < n; j++)
    dp[0, j] = dp[0, j - 1] + grid[0][j];

for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        dp[i, j] = Math.Min(dp[i - 1, j], dp[i, j - 1]) + grid[i][j];
    }
}

Console.WriteLine(dp[m - 1, n - 1]);

A -5

B 0

C -1

D 1

💡 Hint

Negative values can reduce the path sum; carefully track sums at each step.

The minimum path sum is -5 following the path 2 → -3 → -5 → 2 → -1.

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