Minimum Path Sum in Grid in DSA Javascript - Deep Dive

Overview - Minimum Path Sum in Grid

What is it?

Minimum Path Sum in Grid is a problem where you find the smallest total cost to move from the top-left corner to the bottom-right corner of a grid. You can only move either down or right at any point. Each cell in the grid has a number representing the cost to step on it. The goal is to add up the costs along a path that has the smallest sum.

Why it matters

This problem helps us understand how to find the best way through a space with obstacles or costs, like finding the cheapest route on a map. Without this concept, computers would struggle to make efficient decisions in navigation, resource allocation, or planning tasks. It is a foundation for many real-world problems like GPS routing, robotics, and game AI.

Where it fits

Before this, you should know basic arrays and loops. After this, you can learn dynamic programming, pathfinding algorithms like Dijkstra's, and graph traversal techniques.

Mental Model

Core Idea

Find the cheapest path by adding costs step-by-step, choosing only moves down or right, and remembering the best cost to each cell.

Think of it like...

Imagine walking through a city grid where each block has a toll fee. You want to get from your home to a friend's house by paying the least toll, moving only south or east.

Grid example:
┌───┬───┬───┐
│ 1 │ 3 │ 1 │
├───┼───┼───┤
│ 1 │ 5 │ 1 │
├───┼───┼───┤
│ 4 │ 2 │ 1 │
└───┴───┴───┘

Path sums:
Start at top-left (1)
Move right or down, add costs
Goal: bottom-right with smallest sum

Build-Up - 7 Steps

1

Foundation

Understanding the Grid and Moves

Concept: Learn what the grid looks like and allowed moves.

A grid is a 2D array of numbers. You start at the top-left cell (row 0, column 0). You can only move right (same row, next column) or down (next row, same column). Each move adds the cost of the new cell to your total.

Result

You know how to move through the grid and what costs to add.

Understanding allowed moves limits the problem space and simplifies path choices.

2

Foundation

Brute Force Path Exploration

Concept: Try all possible paths to find the minimum sum.

Imagine listing every path from start to end by moving right or down. For each path, add all cell costs. Then pick the smallest total. This works but is slow because paths grow exponentially.

Result

You see the problem is solvable but inefficient with many paths.

Knowing brute force works but is slow motivates smarter methods.

3

Intermediate

Dynamic Programming Table Setup

Concept: Use a table to store minimum sums to each cell.

Create a 2D array same size as grid. Each cell stores the minimum cost to reach it. Start by copying the top-left cell cost. Fill first row by adding costs moving right. Fill first column by adding costs moving down.

Result

You have a table with minimum sums for first row and column.

Pre-filling edges simplifies filling the rest of the table.

4

Intermediate

Filling the DP Table with Recurrence

🤔Before reading on: do you think the minimum cost to a cell depends on the left cell, the top cell, or both? Commit to your answer.

Concept: Each cell's minimum cost depends on the minimum of the cell above and the cell to the left plus current cell cost.

For each cell not in first row or column, calculate minimum sum as: minSum[row][col] = grid[row][col] + min(minSum[row-1][col], minSum[row][col-1]) This means you pick the cheaper path to get there.

Result

The table fills with minimum sums for all cells, ending at bottom-right.

Understanding this recurrence is key to efficient path sum calculation.

5

Intermediate

Extracting the Minimum Path Sum Result

Concept: The answer is the value in the bottom-right cell of the DP table.

After filling the table, the bottom-right cell holds the smallest sum to reach the end. This is your answer.

Result

You get the minimum path sum quickly without checking all paths.

Knowing where to find the final answer in the DP table completes the solution.

6

Advanced

Space Optimization of DP Table

🤔Before reading on: do you think we need to keep the entire DP table or can we use less memory? Commit to your answer.

Concept: You can reduce memory by using a single array to store minimum sums for the current row only.

Since each cell depends only on the left and top cells, keep one array representing the current row's minimum sums. Update it as you move through rows, reusing space.

Result

Memory usage drops from O(m*n) to O(n), where n is number of columns.

Optimizing space is crucial for large grids and shows how dependencies limit data needed.

7

Expert

Handling Obstacles and Variations

🤔Before reading on: do you think the same DP approach works if some cells are blocked or have special rules? Commit to your answer.

Concept: The DP method can adapt to grids with obstacles by marking unreachable cells and skipping them in calculations.

If a cell is blocked, set its DP value to infinity or a sentinel. When calculating neighbors, ignore paths through blocked cells. This changes the recurrence but keeps the DP structure.

Result

You can find minimum path sums even with obstacles or special constraints.

Adapting DP to real-world constraints makes it a powerful, flexible tool.

Under the Hood

The algorithm builds a table where each cell stores the minimum cost to reach it by adding the current cell's cost to the minimum of the costs from the cell above or to the left. This uses overlapping subproblems and optimal substructure, key ideas in dynamic programming. The process avoids recalculating paths by storing intermediate results.

Why designed this way?

Dynamic programming was designed to solve problems with overlapping subproblems efficiently. Instead of exploring all paths (exponential time), it breaks the problem into smaller parts, solves each once, and reuses results. This design balances time and space complexity, making it practical for large grids.

┌─────────────┐
│ Start (0,0) │
└─────┬───────┘
      │
┌─────▼───────┐
│ Fill first  │
│ row & col   │
└─────┬───────┘
      │
┌─────▼───────┐
│ For each    │
│ cell:       │
│ minSum =    │
│ grid + min( │
│ top, left)  │
└─────┬───────┘
      │
┌─────▼───────┐
│ Bottom-right│
│ cell holds  │
│ answer     │
└─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Do you think you can move diagonally in the minimum path sum problem? Commit to yes or no.

Common Belief: You can move diagonally as well as right and down to find the minimum path.

Reality: Only moves to the right or down are allowed; diagonal moves are not permitted.

Why it matters: Allowing diagonal moves changes the problem and solution, leading to incorrect answers if assumed.

Quick: Do you think the minimum path sum is always the sum of the smallest numbers in the grid? Commit to yes or no.

Common Belief: The minimum path sum is just adding the smallest numbers in the grid regardless of path.

Reality: The path must be continuous moving right or down; you cannot pick arbitrary cells with smallest values.

Why it matters: Ignoring path constraints leads to impossible paths and wrong sums.

Quick: Do you think the brute force method is efficient for large grids? Commit to yes or no.

Common Belief: Trying all paths is a good way to solve the problem even for big grids.

Reality: Brute force is exponential and becomes impractical as grid size grows.

Why it matters: Using brute force on large grids causes slow programs and wasted resources.

Quick: Do you think you must store the entire DP table to get the answer? Commit to yes or no.

Common Belief: You need to keep the full table in memory to find the minimum path sum.

Reality: You can optimize space by storing only one row or column at a time.

Why it matters: Not optimizing memory can cause high memory use and inefficiency in large problems.

Expert Zone

1

The order of filling the DP table matters; it must be row-wise or column-wise to ensure dependencies are computed first.

2

When optimizing space, careful indexing is needed to avoid overwriting values before they are used.

3

Handling grids with negative costs requires careful checks to avoid incorrect minimum sums or infinite loops.

When NOT to use

This approach is not suitable if moves other than right or down are allowed, or if the grid is dynamic with changing costs. In such cases, graph algorithms like Dijkstra's or A* are better alternatives.

Production Patterns

In real systems, this method is used for route planning in maps with grid-like layouts, robot path optimization in warehouses, and cost minimization in resource allocation grids. Often combined with heuristics or pruning for speed.

Connections

Dynamic Programming

Minimum Path Sum is a classic example of dynamic programming using overlapping subproblems and optimal substructure.

Understanding this problem deepens comprehension of how to break complex problems into simpler, reusable parts.

Graph Shortest Path Algorithms

The grid can be seen as a graph where each cell is a node connected to right and down neighbors; finding minimum path sum relates to shortest path in weighted graphs.

Recognizing grids as graphs helps apply broader graph algorithms when movement rules change.

Urban Planning and Logistics

Finding minimum cost paths in grids mirrors real-world problems in city navigation and delivery route optimization.

Knowing this algorithm helps design efficient routes and resource use in physical and logistical systems.

Common Pitfalls

#1 Trying to move diagonally in the grid.

Wrong approach:

for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
dp[r][c] = grid[r][c] + Math.min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]); // includes diagonal
}
}

Correct approach:

for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
dp[r][c] = grid[r][c] + Math.min(dp[r-1][c], dp[r][c-1]); // only up and left
}
}

Root cause:

Misunderstanding allowed moves and including diagonal leads to wrong calculations.

#2 Not initializing first row and first column properly.

Wrong approach:

dp[0][0] = grid[0][0];
for (let r = 1; r < rows; r++) dp[r][0] = grid[r][0]; // missing cumulative sum
for (let c = 1; c < cols; c++) dp[0][c] = grid[0][c]; // missing cumulative sum

Correct approach:

dp[0][0] = grid[0][0];
for (let r = 1; r < rows; r++) dp[r][0] = dp[r-1][0] + grid[r][0];
for (let c = 1; c < cols; c++) dp[0][c] = dp[0][c-1] + grid[0][c];

Root cause:

Forgetting to accumulate sums on edges breaks the DP recurrence.

#3 Using brute force recursion without memoization.

Wrong approach:

function minPath(r, c) {
if (r == 0 && c == 0) return grid[0][0];
if (r < 0 || c < 0) return Infinity;
return grid[r][c] + Math.min(minPath(r-1, c), minPath(r, c-1));
}
minPath(rows-1, cols-1);

Correct approach:

Use a DP table or memo object to store results and avoid repeated calculations.

Root cause:

Ignoring overlapping subproblems causes exponential time complexity.

Key Takeaways

Minimum Path Sum in Grid finds the cheapest route from top-left to bottom-right moving only right or down.

Dynamic programming efficiently solves this by storing minimum costs to each cell and building up the solution.

Proper initialization of the first row and column is essential for correct calculations.

Space can be optimized by reusing a single array since each cell depends only on its top and left neighbors.

This problem connects deeply to graph theory and real-world routing challenges, showing the power of algorithmic thinking.

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