Minimum Path Sum in Grid in DSA Javascript - Execution Trace

Concept Flow - Minimum Path Sum in Grid

Start at top-left cell (0,0)

↓

Check if at bottom-right cell?

Yes→Return current path sum

No↓

Move Right or Down

↓

Add cell value

↓

Choose minimum sum path

↓

Repeat until bottom-right reached

Start from the top-left cell, move only right or down, add cell values, and choose the path with the smallest sum until reaching the bottom-right cell.

Execution Sample

DSA Javascript

const minPathSum = (grid) => {
  const m = grid.length, 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];
};

Calculates the minimum path sum from top-left to bottom-right by updating the grid with cumulative minimum sums.

Execution Table

Step	Operation	Cell Updated	Value Added	Grid State	Explanation
1	Initialize first column	(1,0)	3 + 1 = 4	[[1,3,1],[4,5,1],[1,5,1]]	Add cell above (0,0) to current cell (1,0)
2	Initialize first column	(2,0)	1 + 4 = 5	[[1,3,1],[4,5,1],[5,5,1]]	Add cell above (1,0) to current cell (2,0)
3	Initialize first row	(0,1)	3 + 1 = 4	[[1,4,1],[4,5,1],[5,5,1]]	Add cell left (0,0) to current cell (0,1)
4	Initialize first row	(0,2)	1 + 4 = 5	[[1,4,5],[4,5,1],[5,5,1]]	Add cell left (0,1) to current cell (0,2)
5	Update cell	(1,1)	5 + min(4,4) = 9	[[1,4,5],[4,9,1],[5,5,1]]	Add min of top (0,1)=4 and left (1,0)=4 to cell (1,1)
6	Update cell	(1,2)	1 + min(5,9) = 6	[[1,4,5],[4,9,6],[5,5,1]]	Add min of top (0,2)=5 and left (1,1)=9 to cell (1,2)
7	Update cell	(2,1)	5 + min(9,5) = 10	[[1,4,5],[4,9,6],[5,10,1]]	Add min of top (1,1)=9 and left (2,0)=5 to cell (2,1)
8	Update cell	(2,2)	1 + min(6,10) = 7	[[1,4,5],[4,9,6],[5,10,7]]	Add min of top (1,2)=6 and left (2,1)=10 to cell (2,2)
9	Return result	(2,2)	7	[[1,4,5],[4,9,6],[5,10,7]]	Minimum path sum is value at bottom-right cell

💡 Reached bottom-right cell (2,2), minimum path sum found as 7

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
grid	[[1,3,1],[3,5,1],[1,5,1]]	[[1,3,1],[4,5,1],[1,5,1]]	[[1,3,1],[4,5,1],[5,5,1]]	[[1,4,1],[4,5,1],[5,5,1]]	[[1,4,5],[4,5,1],[5,5,1]]	[[1,4,5],[4,9,1],[5,5,1]]	[[1,4,5],[4,9,6],[5,5,1]]	[[1,4,5],[4,9,6],[5,10,1]]	[[1,4,5],[4,9,6],[5,10,7]]	[[1,4,5],[4,9,6],[5,10,7]]

Key Moments - 3 Insights

Why do we first update the first row and first column separately before filling the rest?

Because the first row and column can only be reached from one direction (left for row, top for column), so their sums are cumulative without choice. This is shown in steps 1-4 in the execution_table.

Why do we add the minimum of the top and left cells when updating other cells?

Because from each cell, we can only come from the top or left, so the minimum path sum to the current cell depends on the smaller sum of those two neighbors. This is clear in steps 5-8.

Why does the grid itself get updated instead of using a separate array?

Updating the grid in place saves space and keeps track of the minimum sums directly. The variable_tracker shows how the grid changes after each step.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the updated value at cell (1,1)?

A 9

B 5

C 6

D 4

💡 Hint

Check the 'Value Added' and 'Grid State' columns at step 5 in the execution_table.

At which step does the condition to update cell (2,2) occur?

A Step 7

B Step 8

C Step 6

D Step 9

💡 Hint

Look for the step where cell (2,2) is updated in the 'Cell Updated' column.

If the initial value at cell (0,1) was 2 instead of 3, how would the value at cell (0,2) after step 4 change?

A It would be 3

B It would be 5

C It would be 4

D It would be 6

💡 Hint

Check how the first row is updated cumulatively in steps 3 and 4.

Concept Snapshot

Minimum Path Sum in Grid:
- Start at top-left cell
- Move only right or down
- Update first row and column cumulatively
- For other cells, add min(top, left) cell value
- Result is value at bottom-right cell
- In-place grid update saves space

Full Transcript

This visualization traces the minimum path sum calculation in a grid. We start by updating the first column and first row because they have only one path to reach each cell. Then, for each other cell, we add the minimum of the top and left neighbors to the current cell's value. This process continues until we reach the bottom-right cell, which holds the minimum path sum. The grid is updated in place to keep track of cumulative sums. Key moments include understanding why the first row and column are updated separately and why the minimum of two neighbors is chosen for other cells. The final answer is the value at the bottom-right cell after all updates.

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