Minimum Path Sum in Grid in DSA C# - Build from Scratch

Minimum Path Sum in Grid

📖 Scenario: Imagine you are helping a delivery robot find the easiest path through a city grid. Each block in the city has a cost to cross, and the robot wants to spend the least energy possible to reach its destination.

🎯 Goal: Build a program that finds the minimum total cost for the robot to move from the top-left corner to the bottom-right corner of a grid. The robot can only move right or down.

📋 What You'll Learn

Create a 2D array called grid with exact values

Create an integer variable called rows for the number of rows in grid

Create an integer variable called cols for the number of columns in grid

Use a nested for loop with variables i and j to calculate minimum path sums

Print the minimum path sum using Console.WriteLine

💡 Why This Matters

🌍 Real World

Robots and delivery systems often need to find the easiest or cheapest path through a grid-like map to save energy or time.

💼 Career

Understanding grid traversal and dynamic programming is useful for software engineers working on pathfinding, game development, and optimization problems.

1

Create the grid

Create a 2D integer array called grid with these exact values:
{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}

DSA C#

// Create the grid array with given values
// Your code here

Hint

Use int[,] to create a 2D array and initialize it with the given numbers.

2

Set rows and columns variables

Create an integer variable called rows and set it to the number of rows in grid. Then create an integer variable called cols and set it to the number of columns in grid.

DSA C#

int[,] grid = new int[,] {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
// Create rows and cols variables
// Your code here

Hint

Use GetLength(0) for rows and GetLength(1) for columns.

3

Calculate minimum path sums

Use nested for loops with variables i and j to update grid so each cell contains the minimum path sum to reach it. Remember the robot can only move right or down.

DSA C#

int[,] grid = new int[,] {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
int rows = grid.GetLength(0);
int cols = grid.GetLength(1);
// Calculate minimum path sums using nested for loops
// Your code here

Hint

First update the first column and first row separately, then fill the rest using the minimum of top and left cells.

4

Print the minimum path sum

Print the minimum path sum found at the bottom-right corner of grid using Console.WriteLine.

DSA C#

int[,] grid = new int[,] {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
int rows = grid.GetLength(0);
int cols = grid.GetLength(1);

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] += Math.Min(grid[i - 1, j], grid[i, j - 1]);
    }
}
// Print the minimum path sum
// Your code here

Hint

The answer is the value in the bottom-right cell after updating the grid.

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