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[3][3] = {
  {1, 3, 1},
  {1, 5, 1},
  {4, 2, 1}
};

int dp[3][3];

// Initialize dp
for (int i = 0; i < 3; i++) {
  for (int j = 0; j < 3; j++) {
    dp[i][j] = 0;
  }
}

// Base case
 dp[0][0] = grid[0][0];

// First row
for (int j = 1; j < 3; j++) {
  dp[0][j] = dp[0][j-1] + grid[0][j];
}

// First column
for (int i = 1; i < 3; i++) {
  dp[i][0] = dp[i-1][0] + grid[i][0];
}

// Fill dp
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] ? dp[i-1][j] : dp[i][j-1]) + grid[i][j];
  }
}

printf("%d\n", dp[2][2]);

A 7

B 8

C 9

D 6

💡 Hint

Trace the path from top-left to bottom-right choosing the minimum sum at each step.

The minimum path sum is calculated by dynamic programming. The path is 1 -> 3 -> 1 -> 1 -> 1 with sum 7.

❓ Predict Output

intermediate

Minimum Path Sum with Negative Values

What is the output of this C code calculating minimum path sum in a 2x3 grid with negative values?

DSA C

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

int dp[2][3];

// Initialize dp
for (int i = 0; i < 2; i++) {
  for (int j = 0; j < 3; j++) {
    dp[i][j] = 0;
  }
}

// Base case
 dp[0][0] = grid[0][0];

// First row
for (int j = 1; j < 3; j++) {
  dp[0][j] = dp[0][j-1] + grid[0][j];
}

// First column
for (int i = 1; i < 2; i++) {
  dp[i][0] = dp[i-1][0] + grid[i][0];
}

// Fill dp
for (int i = 1; i < 2; i++) {
  for (int j = 1; j < 3; 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][2]);

A 3

B 1

C 4

D 2

💡 Hint

Consider negative values carefully when adding.

The dp array is: 1 -2 0 5 3 2 Minimum path sum to bottom-right is 2.

🔧 Debug

advanced

Identify the Error in Minimum Path Sum Code

What error does the following C code produce when calculating minimum path sum in a 2x2 grid?

DSA C

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

for (int i = 0; i <= 2; i++) {
  for (int j = 0; j <= 2; j++) {
    dp[i][j] = 0;
  }
}

dp[0][0] = grid[0][0];

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

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

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]);

A Compilation error due to missing semicolon

B Prints incorrect minimum path sum

C Segmentation fault due to out-of-bounds array access

D No error, prints correct result

💡 Hint

Check the loop conditions for array indexing.

The loops use i <= 2 and j <= 2 which access dp[2][2], out of bounds for 2x2 arrays.

❓ Predict Output

advanced

Minimum Path Sum with Single Row Grid

What is the output of this C code calculating minimum path sum in a 1x4 grid?

DSA C

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

// Initialize dp
for (int j = 0; j < 4; j++) {
  dp[0][j] = 0;
}

// Base case
 dp[0][0] = grid[0][0];

// First row
for (int j = 1; j < 4; j++) {
  dp[0][j] = dp[0][j-1] + grid[0][j];
}

printf("%d\n", dp[0][3]);

A 11

B 10

C 9

D 8

💡 Hint

Sum all elements in the single row.

The minimum path sum is sum of all elements: 2+3+1+5=11.

🧠 Conceptual

expert

Minimum Path Sum Algorithm Complexity

What is the time complexity of the dynamic programming solution to the Minimum Path Sum problem in an m x n grid?

A O(m + n)

B O(m * n)

C O(m^2 * n^2)

D O(log(m * n))

💡 Hint

Consider how many cells are processed and how many operations per cell.

The algorithm fills an m by n dp table once, so time complexity is O(m*n).