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 m = 3, n = 3;
int dp[3][3];
dp[0][0] = grid[0][0];
for(int i=1; i<m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for(int j=1; j<n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
for(int i=1; i<m; i++) {
  for(int j=1; j<n; j++) {
    dp[i][j] = std::min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
  }
}
std::cout << dp[m-1][n-1] << std::endl;

A 9

B 8

C 7

D 10

💡 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.

🧠 Conceptual

intermediate

Understanding Movement Constraints in Minimum Path Sum

In the Minimum Path Sum problem, which movements are allowed when moving from the top-left to the bottom-right of the grid?

A Moves can be in any of the four directions: up, down, left, right

B Moves can be to the right, down, or diagonally down-right

C Only moves diagonally down-right are allowed

D Only moves to the right or down are allowed

💡 Hint

Think about the problem constraints that simplify the path choices.

The problem restricts movement to only right or down to ensure a unique path calculation.

🔧 Debug

advanced

Identify the Error in Minimum Path Sum Code

What error will the following code produce when trying to compute the minimum path sum in a grid?

DSA C++

int grid[2][2] = {{1,2},{1,1}};
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 j=1; j<2; j++) dp[j][0] = dp[j-1][0] + grid[j][0];
for(int i=1; i<2; i++) {
  for(int j=1; j<2; j++) {
    dp[i][j] = std::min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
  }
}
std::cout << dp[1][1] << std::endl;

A Wrong output due to incorrect initialization of dp array

B Runtime error due to uninitialized dp values

C Compilation error due to incorrect loop variables

D No error, outputs 3

💡 Hint

Check the initialization of dp array for the first row and column.

The first for loop initializes dp[0][i] but uses i as column index incorrectly; similarly, dp[j][0] initialization uses j as row index but loops incorrectly causing wrong dp values.

🚀 Application

advanced

Minimum Path Sum with Obstacles

Given a grid where some cells are blocked (represented by -1), how would you modify the minimum path sum algorithm to avoid blocked cells?

A Ignore blocked cells and calculate minimum path sum normally

B Skip blocked cells by setting their dp value to a large number and avoid paths through them

C Replace blocked cells with zero and proceed with normal calculation

D Restart calculation from the bottom-right corner

💡 Hint

Think about how to represent unreachable paths in dp table.

Setting dp values of blocked cells to a large number prevents paths from passing through them, effectively avoiding obstacles.

❓ Predict Output

expert

Output of Minimum Path Sum with Large Grid and Negative Values

What is the output of the following C++ code that calculates the minimum path sum in a 2x3 grid with negative values?

DSA C++

int grid[2][3] = {{1,-3,2},{-5,2,1}};
int m = 2, n = 3;
int dp[2][3];
dp[0][0] = grid[0][0];
for(int i=1; i<m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for(int j=1; j<n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
for(int i=1; i<m; i++) {
  for(int j=1; j<n; j++) {
    dp[i][j] = std::min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
  }
}
std::cout << dp[m-1][n-1] << std::endl;

A -1

B 1

C 0

D -3

💡 Hint

Trace the dp table carefully considering negative values.

The dp table values are: 1 -2 0 -4 -2 -1 Minimum path sum is dp[1][2] = -1.

Practice

1. What does the "Minimum Path Sum in Grid" problem ask you to find?

easy

A. The largest sum of numbers along any path in the grid.

B. The shortest path length from top-left to bottom-right.

C. The number of paths from top-left to bottom-right.

D. The smallest sum of numbers along a path from top-left to bottom-right, moving only right or down.

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum sum of values collected when moving from the top-left corner to the bottom-right corner of a grid, moving only right or down.

2. Step 2: Clarify movement constraints

   Only moves to the right or down are allowed, so the path is restricted and the sum depends on chosen cells.

3. Final Answer:

   The smallest sum of numbers along a path from top-left to bottom-right, moving only right or down. -> Option D

4. Quick Check:

   Minimum path sum = smallest sum path [OK]

Hint: Focus on sum along right/down moves only [OK]

Common Mistakes:

• Thinking diagonal moves are allowed
• Looking for maximum sum instead of minimum
• Counting number of paths instead of sum

2. Which of the following C++ code snippets correctly initializes a 2D vector named grid with 3 rows and 4 columns filled with zeros?

easy

A. std::vector grid(3, std::vector<int>(4, 0));

B. std::vector<int> grid(3, std::vector<int>(4, 0));

C. std::vector grid(4, std::vector<int>(3, 0));

D. std::vector grid(3, 4, 0);

Solution

1. Step 1: Understand 2D vector initialization syntax

   To create a 2D vector with 3 rows and 4 columns filled with zeros, we use vector of vectors: outer vector size 3, inner vector size 4, each element 0.

2. Step 2: Check each option

   std::vector grid(3, std::vector<int>(4, 0)); correctly uses std::vector grid(3, std::vector<int>(4, 0)); which means 3 rows, each row is a vector of 4 zeros.

3. Final Answer:

   std::vector grid(3, std::vector<int>(4, 0)); -> Option A

4. Quick Check:

   Correct 2D vector init = std::vector grid(3, std::vector<int>(4, 0)); [OK]

Hint: Use vector of vectors with inner vector size and default value [OK]

Common Mistakes:

• Using wrong vector type for 2D
• Swapping rows and columns sizes
• Trying to pass three arguments to vector constructor

3. What is the output of the following C++ code that calculates the minimum path sum in a 2x2 grid?

std::vector grid = {{1, 3}, {1, 5}};
int m = grid.size();
int n = grid[0].size();
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] += std::min(grid[i-1][j], grid[i][j-1]);
  }
}
std::cout << grid[m-1][n-1] << std::endl;

medium

A. 7

B. 8

C. 9

D. 10

Solution

1. Step 1: Calculate first column cumulative sums

   grid[1][0] = grid[1][0] + grid[0][0] = 1 + 1 = 2

2. Step 2: Calculate first row cumulative sums

   grid[0][1] = grid[0][1] + grid[0][0] = 3 + 1 = 4

3. Step 3: Calculate inner cell minimum path sums

   grid[1][1] = grid[1][1] + min(grid[0][1], grid[1][0]) = 5 + min(4, 2) = 5 + 2 = 7

4. Final Answer:

   7 -> Option A

5. Quick Check:

   Minimum path sum = 7 [OK]

Hint: Update first row and column cumulatively, then inner cells [OK]

Common Mistakes:

• Not updating first row and column before inner cells
• Adding max instead of min
• Mixing indices i and j

4. The following code attempts to compute the minimum path sum in a grid but has a bug. What is the error?

std::vector grid = {{1, 2, 3}, {4, 5, 6}};
int m = grid.size();
int n = grid[0].size();
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] += std::max(grid[i-1][j], grid[i][j-1]);
  }
}
std::cout << grid[m-1][n-1] << std::endl;

medium

A. Wrong loop ranges for i and j

B. Not initializing first row and column

C. Using std::max instead of std::min in inner loop

D. Incorrect grid initialization syntax

Solution

1. Step 1: Check the inner loop operation

   The code uses std::max to update grid[i][j], but the problem requires minimum path sum, so std::min should be used.

2. Step 2: Verify other parts

   First row and column are correctly initialized, loops have correct ranges, and grid initialization is valid.

3. Final Answer:

   Using std::max instead of std::min in inner loop -> Option C

4. Quick Check:

   Use min for minimum path sum [OK]

Hint: Use min, not max, when updating path sums [OK]

Common Mistakes:

• Confusing max and min functions
• Skipping first row/column initialization
• Off-by-one errors in loops

5. Given the grid below, what is the minimum path sum from top-left to bottom-right?

grid = {
  {1, 3, 1, 2},
  {1, 5, 1, 1},
  {4, 2, 1, 3}
};

You can only move right or down. Calculate the minimum sum.

hard

A. 8

B. 10

C. 9

D. 11

Solution

1. Step 1: Compute first row and first column cumulative sums

   First row: [1, 4, 5, 7] (1, 1+3=4, 4+1=5, 5+2=7) First column: [1, 2, 6] (1, 1+1=2, 2+4=6)

2. Step 2: Calculate inner cells minimum path sums

   Row 1, col 1: 5 + min(4,2) = 5 + 2 = 7 Row 1, col 2: 1 + min(5,7) = 1 + 5 = 6 Row 1, col 3: 1 + min(7,6) = 1 + 6 = 7 Row 2, col 1: 2 + min(7,6) = 2 + 6 = 8 Row 2, col 2: 1 + min(6,8) = 1 + 6 = 7 Row 2, col 3: 3 + min(7,7) = 3 + 7 = 10

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Minimum path sum = 10 [OK]

Hint: Fill first row/column, then inner cells with min sums [OK]

Common Mistakes:

• Adding max instead of min
• Incorrect cumulative sums for first row/column
• Misindexing grid cells