Minimum Path Sum in Grid in DSA C#

Mental Model

Find the smallest total by moving only right or down from the top-left to the bottom-right of a grid.

Analogy: Imagine walking through a city grid where each block has a cost to cross. You want to spend the least energy walking from your home at the top-left corner to your friend's house at the bottom-right corner, moving only east or south.

Start:
[1] -> [3] -> [1]
 ↓      ↓      ↓
[1] -> [5] -> [1]
 ↓      ↓      ↓
[4] -> [2] -> [1]

You can only move -> or ↓ to reach the bottom-right.

Dry Run Walkthrough

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]

Goal: Find the path from top-left to bottom-right with the smallest sum of numbers, moving only right or down.

Step 1: Start at top-left cell (0,0) with value 1

[1] -> [3] -> [1]
 ↓      ↓      ↓
[1] -> [5] -> [1]
 ↓      ↓      ↓
[4] -> [2] -> [1]

Why: We begin from the starting point with initial cost 1

Step 2: Fill first row by adding values from left to right: 1, 1+3=4, 4+1=5

[1] -> [4] -> [5]
 ↓      ↓      ↓
[1] -> [5] -> [1]
 ↓      ↓      ↓
[4] -> [2] -> [1]

Why: Only right moves possible in first row, so accumulate sums

Step 3: Fill first column by adding values from top to bottom: 1, 1+1=2, 2+4=6

[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [5] -> [1]
 ↓      ↓      ↓
[6] -> [2] -> [1]

Why: Only down moves possible in first column, so accumulate sums

Step 4: Calculate cell (1,1) as min(top=4, left=2) + 5 = 7

[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [7] -> [1]
 ↓      ↓      ↓
[6] -> [2] -> [1]

Why: Choose the cheaper path to reach (1,1)

Step 5: Calculate cell (1,2) as min(top=5, left=7) + 1 = 6

[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [7] -> [6]
 ↓      ↓      ↓
[6] -> [2] -> [1]

Why: Choose the cheaper path to reach (1,2)

Step 6: Calculate cell (2,1) as min(top=7, left=6) + 2 = 8

[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [7] -> [6]
 ↓      ↓      ↓
[6] -> [8] -> [1]

Why: Choose the cheaper path to reach (2,1)

Step 7: Calculate cell (2,2) as min(top=6, left=8) + 1 = 7

[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [7] -> [6]
 ↓      ↓      ↓
[6] -> [8] -> [7]

Why: Choose the cheaper path to reach bottom-right cell

Result:

Final grid with minimum path sums:
[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [7] -> [6]
 ↓      ↓      ↓
[6] -> [8] -> [7]
Minimum path sum = 7

Annotated Code

DSA C#

using System;

class MinimumPathSum {
    public static int MinPathSum(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;

        // Fill first row
        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j - 1];
        }

        // Fill first column
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }

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

        return grid[m - 1][n - 1];
    }

    static void Main() {
        int[][] grid = new int[][] {
            new int[] {1,3,1},
            new int[] {1,5,1},
            new int[] {4,2,1}
        };

        int result = MinPathSum(grid);
        Console.WriteLine(result);
    }
}

for (int j = 1; j < n; j++) { grid[0][j] += grid[0][j - 1]; }

accumulate sums along the first row since only right moves possible

for (int i = 1; i < m; i++) { grid[i][0] += grid[i - 1][0]; }

accumulate sums along the first column since only down moves possible

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

for each cell, add the minimum of top or left cell sums to current cell value

return grid[m - 1][n - 1];

return the bottom-right cell value which holds the minimum path sum

Output

7

Complexity Analysis

Time: O(m*n) because we visit each cell once to compute minimum sums

Space: O(1) because we update the input grid in place without extra storage

vs Alternative: Compared to a recursive approach without memoization which is exponential, this dynamic programming approach is efficient and uses constant extra space.

Edge Cases

Grid with only one cell

Returns the value of that single cell as the minimum path sum

DSA C#

return grid[m - 1][n - 1];

Grid with one row

Accumulates sums along the row correctly since only right moves are possible

DSA C#

for (int j = 1; j < n; j++) { grid[0][j] += grid[0][j - 1]; }

Grid with one column

Accumulates sums along the column correctly since only down moves are possible

DSA C#

for (int i = 1; i < m; i++) { grid[i][0] += grid[i - 1][0]; }

When to Use This Pattern

When you see a grid and need to find a path with minimum or maximum sum moving only right or down, use dynamic programming to build solutions from smaller subproblems.

Common Mistakes

Mistake: Not initializing the first row and first column sums before filling the rest of the grid
Fix: Explicitly accumulate sums for the first row and first column before processing the rest

Mistake: Using recursion without memoization causing timeouts
Fix: Use bottom-up dynamic programming to avoid repeated calculations

Summary

Finds the smallest sum path from top-left to bottom-right in a grid moving only right or down.

Use when you need to optimize path cost in a grid with movement restrictions.

Build the solution by accumulating minimum sums row-wise and column-wise, then fill the rest using the minimum of top or left neighbors.

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