Minimum Path Sum in Grid in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Path Sum Calculation

What is the output of the following code that calculates the minimum path sum in a 3x3 grid?

DSA Javascript

const grid = [
  [1,3,1],
  [1,5,1],
  [4,2,1]
];

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

console.log(minPathSum(grid));

A 7

B 8

C 10

D 9

💡 Hint

Think about the path that minimizes the sum by moving only right or down.

The minimum path sum is calculated by accumulating the smallest sums from the top-left to bottom-right. The path is 1 → 3 → 1 → 1 → 1, totaling 7.

🧠 Conceptual

intermediate

Understanding Movement Constraints in Minimum Path Sum

In the Minimum Path Sum problem, which moves are allowed when traversing the grid?

A Moves to the left or up only

B Only moves to the right or down

C Moves in all four directions (up, down, left, right)

D Only moves diagonally

💡 Hint

Consider the problem constraints about allowed directions.

The problem restricts movement to only right or down to ensure a unique path from top-left to bottom-right.

❓ Predict Output

advanced

Output of Minimum Path Sum with Negative Values

What is the output of the code below that calculates the minimum path sum in a grid containing negative values?

DSA Javascript

const grid = [
  [2, -3, 1],
  [5, -10, 2],
  [1, 2, 1]
];

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

console.log(minPathSum(grid));

A -1

B 1

C -8

D 0

💡 Hint

Negative values can reduce the path sum; carefully track sums along the path.

The minimum path sum is -8, following the path 2 → -3 → -10 → 2 → 1, totaling -8.

🔧 Debug

advanced

Identify the Error in Minimum Path Sum Code

What error does the following code produce when run?

DSA Javascript

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

const grid = [[1,2],[1,1]];
console.log(minPathSum(grid));

A TypeError: Cannot read property '0' of undefined

B ReferenceError: grid is not defined

C SyntaxError: Unexpected token '}'

D Output: 3

💡 Hint

Check the loop conditions and array indexing carefully.

The loops use <= which causes index out of bounds, leading to undefined access and TypeError.

🚀 Application

expert

Minimum Path Sum with Obstacles

Given a grid where some cells are blocked (represented by -1), which modification correctly calculates the minimum path sum avoiding blocked cells? Blocked cells cannot be part of the path.

DSA Javascript

const grid = [
  [1, 3, 1],
  [1, -1, 1],
  [4, 2, 1]
];

function minPathSumWithObstacles(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const dp = Array.from({ length: m }, () => Array(n).fill(Infinity));
  if (grid[0][0] === -1) return -1;
  dp[0][0] = grid[0][0];
  for (let i = 1; i < m; i++) {
    if (grid[i][0] === -1) break;
    dp[i][0] = dp[i-1][0] + grid[i][0];
  }
  for (let j = 1; j < n; j++) {
    if (grid[0][j] === -1) break;
    dp[0][j] = dp[0][j-1] + grid[0][j];
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (grid[i][j] === -1) continue;
      dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
    }
  }
  return dp[m-1][n-1] === Infinity ? -1 : dp[m-1][n-1];
}

console.log(minPathSumWithObstacles(grid));

A 6

B 8

C -1

D 7

💡 Hint

Blocked cells should not be included in the path and cause path to stop if no alternative exists.

The minimum path sum avoiding the blocked cell (-1) is 7, following the path 1 → 3 → 1 → 1 → 1.

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