Minimum Path Sum in Grid in DSA C# - Time & Space Complexity

Time Complexity: Minimum Path Sum in Grid

O(m x n)

Understanding Time Complexity

We want to understand how the time needed to find the minimum path sum in a grid changes as the grid size grows.

Specifically, how does the number of steps grow when the grid gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public int MinPathSum(int[][] grid) {
    int m = grid.Length, n = grid[0].Length;
    for (int i = 1; i < m; i++)
        grid[i][0] += grid[i - 1][0];
    for (int j = 1; j < n; j++)
        grid[0][j] += grid[0][j - 1];
    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];
}
    

This code finds the minimum sum path from the top-left to the bottom-right of a grid, moving only down or right.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops traversing the grid cells.
• How many times: The outer loop runs m-1 times, the inner loop runs n-1 times, so roughly m x n times.

How Execution Grows With Input

As the grid size grows, the number of operations grows roughly with the total number of cells.

Input Size (m x n)	Approx. Operations
10 x 10	About 100 operations
100 x 100	About 10,000 operations
1000 x 1000	About 1,000,000 operations

Pattern observation: Doubling the grid size roughly quadruples the operations, showing growth proportional to the number of cells.

Final Time Complexity

Time Complexity: O(m x n)

This means the time needed grows proportionally with the total number of cells in the grid.

Common Mistake

[X] Wrong: "The time grows only with the number of rows or columns, not both."

[OK] Correct: The code visits every cell in the grid, so both rows and columns affect the total steps, not just one dimension.

Interview Connect

Understanding this time complexity helps you explain how efficient your solution is when working with grids, a common problem type.

Self-Check

"What if we could only move right or down but the grid was sparse with many blocked cells? How would the time complexity change?"

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