Minimum Path Sum in Grid in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the goal of the Minimum Path Sum problem in a grid?

To find the path from the top-left corner to the bottom-right corner of a grid that has the smallest sum of all numbers along the path, moving only down or right.

beginner

Which moves are allowed when finding the minimum path sum in a grid?

You can only move either one step down or one step right at any point in the grid.

intermediate

How can dynamic programming help solve the Minimum Path Sum problem?

Dynamic programming stores the minimum path sums for each cell based on previously computed cells, avoiding repeated calculations and efficiently finding the overall minimum path sum.

beginner

What is the base case when using dynamic programming for the Minimum Path Sum problem?

The base case is the top-left cell itself, where the minimum path sum is just the value of that cell because it is the starting point.

intermediate

How do you compute the minimum path sum for a cell not in the first row or first column?

Take the minimum of the path sums from the cell above and the cell to the left, then add the current cell's value.

In the Minimum Path Sum problem, which directions can you move?

A Diagonally

B Down or Right

C Up or Left

D Any direction

You can only move down or right to find the minimum path sum.

What is the minimum path sum for the starting cell (top-left corner)?

A The value of the starting cell

B 0

C The sum of all cells

D Infinity

The starting cell's minimum path sum is its own value.

Which technique is commonly used to solve the Minimum Path Sum problem efficiently?

A Dynamic programming

B Brute force recursion

C Greedy algorithm

D Sorting

Dynamic programming avoids repeated calculations by storing intermediate results.

How do you calculate the minimum path sum for a cell in the middle of the grid?

A Only consider the cell above

B Add the current cell value to the maximum of the sums from the cell above and the cell to the left

C Add the current cell value to the sum of the cells diagonally

D Add the current cell value to the minimum of the sums from the cell above and the cell to the left

You take the minimum of the two possible previous paths and add the current cell's value.

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

A O(m^2 * n^2)

B O(m + n)

C O(m * n)

D O(1)

The solution visits each cell once, so time complexity is proportional to the number of cells.

Explain how to use dynamic programming to find the minimum path sum in a grid.

Think about building the solution step by step from the start.

Describe the base cases and how to fill the first row and first column in the Minimum Path Sum problem.

Consider how you can only move right in the first row and only down in the first column.

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