Minimum Path Sum in Grid in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the first cell of the dp grid with the grid's first cell value.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

A(

B[

C{

D.

Attempts:

3 left

💡 Hint

Common Mistakes

Using parentheses () instead of square brackets []

Using dot notation which doesn't work for array indices

We use square brackets [] to access elements in a 2D array in JavaScript.

2fill in blank

medium

Complete the code to fill the first row of the dp grid by accumulating sums from the left.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

A*

B-

C+

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition

Using division which is not meaningful here

We add the current grid value to the sum from the left cell to accumulate the path sum.

3fill in blank

hard

Fix the error in the code to correctly compute the minimum path sum for each cell.

DSA Javascript

dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) [1] grid[i][j];

Drag options to blanks, or click blank then click option'

A-

B/

C*

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition

Using division which is incorrect here

We add the current grid value to the minimum of the top and left dp cells to get the minimum path sum.

4fill in blank

hard

Fill both blanks to complete the loops that fill the dp grid starting from row 1 and column 1.

DSA Javascript

for (let i = 1; i [1] rows; i++) {
  for (let j = 1; j [2] cols; j++) {
    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
  }
}

Drag options to blanks, or click blank then click option'

A<

B<=

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= which causes index out of range errors

Using > or >= which won't run the loops correctly

We use less than < to loop from 1 up to but not including rows and cols, matching array indices.

5fill in blank

hard

Fill both blanks to return the minimum path sum from the bottom-right cell of the dp grid.

DSA Javascript

return dp[1][2];

Drag options to blanks, or click blank then click option'

A[rows - 1]

B[cols - 1]

C[rows]

D[cols]

Attempts:

3 left

💡 Hint

Common Mistakes

Using dp[rows][cols] which is out of bounds

Mixing up rows and cols indices

We access dp[rows - 1][cols - 1] to get the minimum path sum at the bottom-right corner.

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