Minimum Path Sum in Grid in DSA Javascript - 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 possible sum of all numbers along the path, moving only right or down.

beginner

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

You can only move either one step to the right or one step down at each move.

intermediate

Why is dynamic programming useful for solving the Minimum Path Sum problem?

Because it stores the minimum path sums for smaller parts of the grid to avoid repeating calculations, making the solution efficient.

beginner

What is the base case when using dynamic programming for Minimum Path Sum in a grid?

The top-left cell's minimum path sum is its own value since it is the starting point.

intermediate

How do you calculate the minimum path sum for a cell not in the first row or 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 Right and Up

B Left and Up

C Right and Down

D Left and Down

You can only move right or down to reach the bottom-right corner.

What is the minimum path sum for the starting cell in the grid?

A The value of the starting cell

B Zero

C The sum of all cells in the first row

D The sum of all cells in the first column

The starting cell's minimum path sum is its own value because it's the starting point.

Which technique helps avoid repeated calculations in the Minimum Path Sum problem?

A Dynamic programming

B Brute force

C Greedy algorithm

D Backtracking

Dynamic programming stores results of subproblems to avoid recalculations.

How do you find the minimum path sum for a cell inside the grid (not on edges)?

A Use only the value of the cell itself

B Add the cell's value to the minimum of the sums from the top or left cells

C Add the cell's value to the sum of the top and left cells

D Add the cell's value to the maximum of the sums from the top or left cells

You add the current cell's value to the smaller of the two possible previous path sums.

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

A O(m + n)

B O(m^n)

C O(n!)

D O(m * n)

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 movement restrictions and why they matter in the Minimum Path Sum problem.

Consider how movement limits the paths you can take.

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 smallest 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 largest 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 a 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 B

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 path sum
• Counting number of paths instead of sum
• Ignoring movement restrictions (only right/down)

2. Which of the following JavaScript code snippets correctly initializes a 2D array dp for dynamic programming with the same size as grid?

easy

A. const dp = Array.from({ length: grid.length }, () => Array(grid[0].length).fill(0));

B. const dp = new Array(grid.length).fill(new Array(grid[0].length));

C. const dp = Array(grid.length).fill(Array(grid[0].length).fill(0));

D. const dp = Array(grid[0].length).map(() => Array(grid.length).fill(0));

Solution

1. Step 1: Understand 2D array initialization

   Using Array.from with a mapping function creates independent inner arrays, avoiding shared references.

2. Step 2: Analyze each option

   const dp = Array(grid.length).fill(Array(grid[0].length).fill(0)); uses fill with an array, causing all rows to reference the same array (wrong). const dp = Array.from({ length: grid.length }, () => Array(grid[0].length).fill(0)); correctly creates independent arrays. const dp = new Array(grid.length).fill(new Array(grid[0].length)); fills with undefined arrays (wrong). const dp = Array(grid.length).map(() => Array(grid[0].length).fill(0)); uses map on an uninitialized array, which returns empty array (wrong).

3. Final Answer:

   const dp = Array.from({ length: grid.length }, () => Array(grid[0].length).fill(0)); -> Option A

4. Quick Check:

   Use Array.from with function for independent rows [OK]

Hint: Use Array.from with function to avoid shared inner arrays [OK]

Common Mistakes:

• Using fill with array causes shared references
• Using map on uninitialized array returns empty
• Not initializing inner arrays properly

3. What is the output of the following code?

const grid = [[1,3,1],[1,5,1],[4,2,1]];
function minPathSum(grid) {
  const m = grid.length, n = grid[0].length;
  const dp = Array.from({ length: m }, () => Array(n).fill(0));
  dp[0][0] = grid[0][0];
  for(let i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
  for(let j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
  for(let i = 1; i < m; i++) {
    for(let j = 1; j < n; j++) {
      dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
    }
  }
  return dp[m-1][n-1];
}
console.log(minPathSum(grid));

medium

A. 7

B. 8

C. 10

D. 9

Solution

1. Step 1: Initialize dp with first row and column sums

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

2. Step 2: Fill dp for other cells using minimum of top or left

   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 calculated = 7 [OK]

Hint: Fill dp row and column first, then use min of top and left [OK]

Common Mistakes:

• Adding max instead of min
• Incorrect initialization of dp edges
• Mixing up indices in loops

4. Find the error in the following code snippet for minimum path sum and select the fix:

function minPathSum(grid) {
  const m = grid.length, n = grid[0].length;
  const dp = Array(m).fill(Array(n).fill(0));
  dp[0][0] = grid[0][0];
  for(let i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
  for(let j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
  for(let i = 1; i < m; i++) {
    for(let j = 1; j < n; j++) {
      dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
    }
  }
  return dp[m-1][n-1];
}

medium

A. Initialize dp with zeros using nested for loops

B. Change Math.min to Math.max in inner loop

C. Replace dp initialization with Array.from to avoid shared references

D. Remove dp array and use grid directly

Solution

1. Step 1: Identify the dp initialization problem

   Using Array(m).fill(Array(n).fill(0)) causes all rows to reference the same inner array, leading to incorrect updates.

2. Step 2: Fix dp initialization

   Use Array.from({ length: m }, () => Array(n).fill(0)) to create independent inner arrays for each row.

3. Final Answer:

   Replace dp initialization with Array.from to avoid shared references -> Option C

4. Quick Check:

   Use Array.from for independent rows in 2D array [OK]

Hint: Avoid fill with arrays; use Array.from for 2D arrays [OK]

Common Mistakes:

• Using fill with arrays causing shared references
• Changing min to max breaks logic
• Removing dp causes wrong results

5. Given a grid:

[[2,1,3],[6,5,4],[7,8,9]]

What is the minimum path sum if you can only move right or down from the top-left to bottom-right?

hard

A. 18

B. 20

C. 21

D. 19

Solution

1. Step 1: Initialize dp edges

   dp[0][0]=2; first row: dp[0][1]=2+1=3; dp[0][2]=3+3=6; first column: dp[1][0]=2+6=8; dp[2][0]=8+7=15;

2. Step 2: Fill dp inner cells

   dp[1][1]=min(dp[0][1],dp[1][0])+5=min(3,8)+5=8; dp[1][2]=min(dp[0][2],dp[1][1])+4=min(6,8)+4=10; dp[2][1]=min(dp[1][1],dp[2][0])+8=min(8,15)+8=16; dp[2][2]=min(dp[1][2],dp[2][1])+9=min(10,16)+9=19;

3. Step 3: Verify final dp value

   The bottom-right dp value is 19, but check if a better path exists by tracing:

4. Step 4: Trace path for minimum sum

   Path: 2 -> 1 -> 3 -> 4 -> 9 sums to 19; Path: 2 -> 1 -> 5 -> 4 -> 9 sums to 21; Path: 2 -> 6 -> 5 -> 4 -> 9 sums to 26; Path: 2 -> 6 -> 8 -> 9 sums to 25; So minimum is 19.

5. Final Answer:

   19 -> Option D

6. Quick Check:

   Minimum path sum calculated = 19 [OK]

Hint: Fill dp edges first, then inner cells with min of top and left [OK]

Common Mistakes:

• Not initializing first row and column correctly
• Adding max instead of min
• Misreading grid values