Minimum Path Sum in Grid in DSA Typescript

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 find the cheapest path from your home (top-left) to your friend's house (bottom-right) by only moving east or south.

Start:
[1] -> [3] -> [1]
 ↓      ↓      ↓
[1] -> [5] -> [1]
 ↓      ↓      ↓
[4] -> [2] -> [1]

You can only move -> or ↓ to reach the bottom-right.

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: Start at top-left cell (0,0) with value 1

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

Why: We begin from the starting point with initial cost 1.

Step 2: Calculate minimum path sums for first row by adding left cell sums

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

Why: Only right moves possible in first row, so sums accumulate.

Step 3: Calculate minimum path sums for first column by adding above cell sums

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

Why: Only down moves possible in first column, so sums accumulate.

Step 4: Calculate cell (1,1) as min(top, left) + current value: min(4,2)+5=7

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

Why: Choose cheaper path between coming from top or left.

Step 5: Calculate cell (1,2): min(top, left)+value = min(5,7)+1=6

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

Why: Pick minimum sum path to this cell.

Step 6: Calculate cell (2,1): min(top, left)+value = min(7,6)+2=8

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

Why: Choose minimum path sum to this cell.

Step 7: Calculate cell (2,2): min(top, left)+value = min(6,8)+1=7

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

Why: Final cell sum is minimum path sum to bottom-right.

Result:

[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [7] -> [6]
 ↓      ↓      ↓
[6] -> [8] -> [7]
Minimum path sum = 7

Annotated Code

DSA Typescript

class Solution {
  minPathSum(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;

    // Update first row sums
    for (let j = 1; j < n; j++) {
      grid[0][j] += grid[0][j - 1];
    }

    // Update first column sums
    for (let i = 1; i < m; i++) {
      grid[i][0] += grid[i - 1][0];
    }

    // Update rest of grid with min path sums
    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];
  }
}

// Driver code
const grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
];
const sol = new Solution();
console.log(sol.minPathSum(grid));

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

Accumulate sums along the first row since only right moves possible

for (let i = 1; i < m; i++) { grid[i][0] += grid[i - 1][0]; }

Accumulate sums along the first column since only down moves possible

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]); } }

For each cell, add the minimum of top or left cell sums to current cell value

return grid[m - 1][n - 1];

Return the minimum path sum at bottom-right cell

Output

7

Complexity Analysis

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

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

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

Edge Cases

Empty grid

Function returns undefined or error since no cells to process

DSA Typescript

const m = grid.length; const n = grid[0].length;

Single cell grid [[5]]

Returns the single cell value 5 as minimum path sum

DSA Typescript

return grid[m - 1][n - 1];

Grid with one row [[1,2,3]]

Accumulates sums along the row correctly, returns 6

DSA Typescript

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

When to Use This Pattern

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

Common Mistakes

Mistake: Not updating the first row and first column separately before filling the rest of the grid
Fix: Accumulate sums along 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

Summary

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

Use when you need the cheapest path sum in a grid with movement constraints.

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