Minimum Path Sum in Grid in DSA Javascript

Mental Model

Find the smallest total by moving only right or down from the top-left to the bottom-right of a grid.

Analogy: Imagine walking through a city grid where each block has a cost to cross. You want to spend the least energy walking from your home (top-left) to your friend's house (bottom-right), only moving east or south.

Start at top-left corner (S), move only -> or ↓, reach bottom-right corner (E).

[S] -> [ ] -> [ ]
 ↓     ↓     ↓
[ ] -> [ ] -> [E]

Dry Run Walkthrough

Input: grid: [[1,3,1],[1,5,1],[4,2,1]]

Goal: Find the minimum sum path from top-left to bottom-right moving only right or down.

Step 1: Initialize first row by accumulating sums moving right

[1] -> [4] -> [5]
[1] -> [5] -> [1]
[4] -> [2] -> [1]

Why: We can only move right in the first row, so sums accumulate from left to right.

Step 2: Initialize first column by accumulating sums moving down

[1] -> [4] -> [5]
[2] -> [5] -> [1]
[6] -> [2] -> [1]

Why: We can only move down in the first column, so sums accumulate from top to bottom.

Step 3: Calculate minimum path sum for cell (1,1) by choosing min from top or left + current cell

[1] -> [4] -> [5]
[2] -> [7] -> [1]
[6] -> [2] -> [1]

Why: We pick the smaller sum path to reach this cell.

Step 4: Calculate minimum path sum for cell (1,2)

[1] -> [4] -> [5]
[2] -> [7] -> [8]
[6] -> [2] -> [1]

Why: Again, choose the smaller sum path from top or left.

Step 5: Calculate minimum path sum for cell (2,1)

[1] -> [4] -> [5]
[2] -> [7] -> [8]
[6] -> [8] -> [1]

Why: Pick minimum sum path from top or left.

Step 6: Calculate minimum path sum for cell (2,2)

[1] -> [4] -> [5]
[2] -> [7] -> [8]
[6] -> [8] -> [9]

Why: Final cell sum is min(top, left) + current cell value.

Result:

Final grid with minimum path sums:
[1] -> [4] -> [5]
[2] -> [7] -> [8]
[6] -> [8] -> [9]
Minimum path sum = 9

Annotated Code

DSA Javascript

class Grid {
  constructor(grid) {
    this.grid = grid;
    this.rows = grid.length;
    this.cols = grid[0].length;
  }

  minPathSum() {
    // Update first row sums
    for (let c = 1; c < this.cols; c++) {
      this.grid[0][c] += this.grid[0][c - 1];
    }

    // Update first column sums
    for (let r = 1; r < this.rows; r++) {
      this.grid[r][0] += this.grid[r - 1][0];
    }

    // Update rest of the grid
    for (let r = 1; r < this.rows; r++) {
      for (let c = 1; c < this.cols; c++) {
        this.grid[r][c] += Math.min(this.grid[r - 1][c], this.grid[r][c - 1]);
      }
    }

    return this.grid[this.rows - 1][this.cols - 1];
  }

  printGrid() {
    for (let r = 0; r < this.rows; r++) {
      console.log(this.grid[r].join(' -> '));
    }
  }
}

// Driver code
const inputGrid = [[1,3,1],[1,5,1],[4,2,1]];
const grid = new Grid(inputGrid);
const minSum = grid.minPathSum();
grid.printGrid();
console.log('Minimum path sum =', minSum);

for (let c = 1; c < this.cols; c++) { this.grid[0][c] += this.grid[0][c - 1]; }

accumulate sums along the first row moving right

for (let r = 1; r < this.rows; r++) { this.grid[r][0] += this.grid[r - 1][0]; }

accumulate sums along the first column moving down

for (let r = 1; r < this.rows; r++) { for (let c = 1; c < this.cols; c++) { this.grid[r][c] += Math.min(this.grid[r - 1][c], this.grid[r][c - 1]); } }

update each cell with minimum sum from top or left neighbor plus current cell value

return this.grid[this.rows - 1][this.cols - 1];

return the minimum path sum at bottom-right corner

Output

1 -> 4 -> 5

2 -> 7 -> 8

6 -> 8 -> 9

Minimum path sum = 9

Complexity Analysis

Time: O(m*n) because we visit each cell once to compute minimum sums

Space: O(1) because we update the grid in place without extra storage

vs Alternative: Compared to recursive solutions without memoization which are exponential, this dynamic programming approach is efficient and uses constant extra space.

Edge Cases

Grid with only one cell

Returns the value of that single cell as the minimum path sum

DSA Javascript

for (let c = 1; c < this.cols; c++) { this.grid[0][c] += this.grid[0][c - 1]; }

Grid with one row

Accumulates sums moving right along the single row

DSA Javascript

for (let c = 1; c < this.cols; c++) { this.grid[0][c] += this.grid[0][c - 1]; }

Grid with one column

Accumulates sums moving down along the single column

DSA Javascript

for (let r = 1; r < this.rows; r++) { this.grid[r][0] += this.grid[r - 1][0]; }

When to Use This Pattern

When you see a grid and need to find a path with minimum cost moving only right or down, use dynamic programming to build up solutions from smaller subproblems.

Common Mistakes

Mistake: Not initializing the first row and first column sums before filling the rest of the grid
Fix: Explicitly accumulate sums for the first row and first column before processing inner cells

Mistake: Using max instead of min when choosing between top and left cells
Fix: Use Math.min to pick the smaller sum path to ensure minimum total

Summary

Calculates the smallest sum path from top-left to bottom-right in a grid moving only right or down.

Use when you need to find minimum cost paths in grid-like problems with restricted moves.

Build the solution by accumulating minimum sums row-wise and column-wise, then fill the rest using the minimum of top or left neighbors.

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