Bird
Raised Fist0
DSA Cprogramming~5 mins

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

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Time Complexity: Minimum Path Sum in Grid
O(m x n)
Understanding Time Complexity

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

How does the number of steps grow when the grid gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


int minPathSum(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = gridColSize[0];
    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] += (grid[i-1][j] < grid[i][j-1]) ? grid[i-1][j] : grid[i][j-1];
        }
    }
    return grid[m-1][n-1];
}

This code calculates 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: Outer loop runs m-1 times, 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 10About 100 operations
100 x 100About 10,000 operations
1000 x 1000About 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 to the total number of cells in the grid.

Common Mistake

[X] Wrong: "The time grows exponentially because there are many paths."

[OK] Correct: The code uses dynamic programming to avoid repeating calculations, so it only visits each cell once, not all paths.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming improves efficiency by avoiding repeated work, a key skill in problem solving.

Self-Check

"What if we allowed moving diagonally as well? How would the time complexity change?"

Practice

(1/5)
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. Which is true?
easy
A. Find the path with the smallest sum moving only right or down.
B. Find the path with the largest sum moving in any direction.
C. Find the path with the smallest sum moving diagonally only.
D. Find the path with the smallest sum moving left or up.

Solution

  1. Step 1: Understand the movement constraints

    The problem allows moving only right or down from each cell in the grid.

  2. Step 2: Identify the goal

    The goal is to find the path from the top-left corner to the bottom-right corner with the minimum sum of all numbers on the path.

  3. Final Answer:

    Find the path with the smallest sum moving only right or down. -> Option A

  4. Quick Check:

    Minimum path sum = smallest sum with right/down moves [OK]
Hint: Remember: only right or down moves allowed [OK]
Common Mistakes:
  • Thinking diagonal moves are allowed
  • Looking for maximum sum instead of minimum
  • Moving left or up which is not allowed
2. Which of the following C code snippets correctly initializes a 2D array named grid with 3 rows and 3 columns filled with zeros?
easy
A. int grid[3][3] = {1};
B. int grid[3][3] = {{1}};
C. int grid[3][3]; memset(grid, 0, sizeof(grid));
D. int grid[3][3] = { {0,0,0}, {0,0,0}, {1,1,1} };

Solution

  1. Step 1: Understand array initialization in C

    Initializing a 2D array with zeros can be done by setting all elements to zero using memset after declaration.

  2. Step 2: Check each option

    int grid[3][3]; memset(grid, 0, sizeof(grid)); declares the array and then uses memset to set all bytes to zero, correctly initializing all elements to zero.

  3. Final Answer:

    int grid[3][3]; memset(grid, 0, sizeof(grid)); -> Option C

  4. Quick Check:

    memset sets all elements to zero [OK]
Hint: Use memset for zeroing arrays in C [OK]
Common Mistakes:
  • Using {1} only initializes first element
  • Confusing single braces with double braces
  • Not including string.h for memset
3. What is the output of the following C code that calculates the minimum path sum in a 2x2 grid?
int grid[2][2] = {{1, 3}, {1, 5}};
int dp[2][2];
dp[0][0] = grid[0][0];
for(int i=1; i<2; i++) dp[0][i] = dp[0][i-1] + grid[0][i];
for(int i=1; i<2; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for(int i=1; i<2; i++) {
  for(int j=1; j<2; j++) {
    dp[i][j] = (dp[i-1][j] < dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]) + grid[i][j];
  }
}
printf("%d\n", dp[1][1]);
medium
A. 10
B. 8
C. 9
D. 7

Solution

  1. Step 1: Calculate first row and column sums

    dp[0][0] = 1
    dp[0][1] = 1 + 3 = 4
    dp[1][0] = 1 + 1 = 2

  2. Step 2: Calculate dp[1][1]

    Minimum of dp[0][1] = 4 and dp[1][0] = 2 is 2
    dp[1][1] = 2 + 5 = 7

  3. Final Answer:

    7 -> Option D

  4. Quick Check:

    Minimum path sum = 7 [OK]
Hint: Fill dp row and column first, then inner cells [OK]
Common Mistakes:
  • Adding max instead of min
  • Incorrect dp initialization
  • Off-by-one errors in loops
4. The following code attempts to compute the minimum path sum in a 3x3 grid but has a bug. What is the bug?
int grid[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
int dp[3][3];
dp[0][0] = grid[0][0];
for(int i=1; i<3; i++) dp[0][i] = dp[0][i-1] + grid[0][i];
for(int i=1; i<3; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for(int i=1; i<3; i++) {
  for(int j=1; j<3; j++) {
    dp[i][j] = dp[i-1][j] + dp[i][j-1] + grid[i][j];
  }
}
medium
A. The dp update adds both dp[i-1][j] and dp[i][j-1] instead of taking the minimum.
B. The loops start from 1 instead of 0.
C. The dp array is not initialized to zero.
D. The grid values are not accessed correctly.

Solution

  1. Step 1: Analyze dp update formula

    The code adds dp[i-1][j] and dp[i][j-1] together plus grid[i][j], which is incorrect.

  2. Step 2: Correct dp update

    It should take the minimum of dp[i-1][j] and dp[i][j-1], then add grid[i][j].

  3. Final Answer:

    The dp update adds both dp[i-1][j] and dp[i][j-1] instead of taking the minimum. -> Option A

  4. Quick Check:

    Use min(dp[i-1][j], dp[i][j-1]) + grid[i][j] [OK]
Hint: Use min, not sum, of top and left dp cells [OK]
Common Mistakes:
  • Adding dp values instead of min
  • Wrong loop ranges
  • Not initializing dp[0][0]
5. Given a 3x3 grid:
int grid[3][3] = {
  {1, 3, 1},
  {1, 5, 1},
  {4, 2, 1}
};

Write the minimum path sum from top-left to bottom-right moving only right or down. What is the minimum sum?
hard
A. 8
B. 7
C. 9
D. 10

Solution

  1. Step 1: Calculate dp first row and column

    dp[0][0] = 1
    dp[0][1] = 1+3=4
    dp[0][2] = 4+1=5
    dp[1][0] = 1+1=2
    dp[2][0] = 2+4=6

  2. Step 2: Calculate inner dp 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 B

  4. Quick Check:

    Minimum path sum = 7 [OK]
Hint: Fill dp row-wise and column-wise, then inner cells [OK]
Common Mistakes:
  • Choosing wrong min between top and left
  • Incorrect dp initialization
  • Misreading grid values
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard