Unique Paths in Grid DP in DSA Typescript

Mental Model

We count how many ways to reach each cell by adding ways from the top and left cells. This builds up the total paths step by step.

Analogy: Imagine walking on a city grid where you can only move right or down. To reach a building, you add the number of ways you could have come from the building above and the building to the left.

Start grid (3x3):
[1] -> [ ] -> [ ]
 ↓      ↓      ↓
[ ] -> [ ] -> [ ]
 ↓      ↓      ↓
[ ] -> [ ] -> [ ]

[1] means starting point with 1 way, empty means unknown ways.

Dry Run Walkthrough

Input: Grid size: 3 rows x 3 columns

Goal: Find total unique paths from top-left corner to bottom-right corner moving only right or down

Step 1: Initialize first row with 1s because only one way to move right along top row

[1] -> [1] -> [1]
 ↓      ↓      ↓
[ ] -> [ ] -> [ ]
 ↓      ↓      ↓
[ ] -> [ ] -> [ ]

Why: Only one way to reach cells in first row: keep moving right

Step 2: Initialize first column with 1s because only one way to move down along left column

[1] -> [1] -> [1]
 ↓      ↓      ↓
[1] -> [ ] -> [ ]
 ↓      ↓      ↓
[1] -> [ ] -> [ ]

Why: Only one way to reach cells in first column: keep moving down

Step 3: Calculate ways for cell (1,1) by adding ways from top (0,1) and left (1,0)

[1] -> [1] -> [1]
 ↓      ↓      ↓
[1] -> [2] -> [ ]
 ↓      ↓      ↓
[1] -> [ ] -> [ ]

Why: Paths to (1,1) = paths from above + paths from left = 1 + 1 = 2

Step 4: Calculate ways for cell (1,2) by adding ways from top (0,2) and left (1,1)

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

Why: Paths to (1,2) = 1 (top) + 2 (left) = 3

Step 5: Calculate ways for cell (2,1) by adding ways from top (1,1) and left (2,0)

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

Why: Paths to (2,1) = 2 (top) + 1 (left) = 3

Step 6: Calculate ways for cell (2,2) by adding ways from top (1,2) and left (2,1)

[1] -> [1] -> [1]
 ↓      ↓      ↓
[1] -> [2] -> [3]
 ↓      ↓      ↓
[1] -> [3] -> [6]

Why: Paths to (2,2) = 3 (top) + 3 (left) = 6

Result:

Final grid with path counts:
[1] -> [1] -> [1]
 ↓      ↓      ↓
[1] -> [2] -> [3]
 ↓      ↓      ↓
[1] -> [3] -> [6]

Total unique paths = 6

Annotated Code

DSA Typescript

class UniquePaths {
  static uniquePaths(m: number, n: number): number {
    if (m === 0 || n === 0) return 0;
    const dp: number[][] = Array.from({ length: m }, () => Array(n).fill(0));

    // Initialize first row with 1s
    for (let col = 0; col < n; col++) {
      dp[0][col] = 1;
    }

    // Initialize first column with 1s
    for (let row = 0; row < m; row++) {
      dp[row][0] = 1;
    }

    // Fill the dp table
    for (let row = 1; row < m; row++) {
      for (let col = 1; col < n; col++) {
        dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
      }
    }

    return dp[m - 1][n - 1];
  }
}

// Driver code
const m = 3;
const n = 3;
const result = UniquePaths.uniquePaths(m, n);
console.log(`Total unique paths in a ${m}x${n} grid: ${result}`);

for (let col = 0; col < n; col++) { dp[0][col] = 1; }

Initialize first row with 1s because only one way to move right

for (let row = 0; row < m; row++) { dp[row][0] = 1; }

Initialize first column with 1s because only one way to move down

for (let row = 1; row < m; row++) { for (let col = 1; col < n; col++) { dp[row][col] = dp[row - 1][col] + dp[row][col - 1]; } }

Calculate paths for each cell by adding ways from top and left cells

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

Return total unique paths to bottom-right corner

Output

Total unique paths in a 3x3 grid: 6

Complexity Analysis

Time: O(m*n) because we fill each cell in the grid once

Space: O(m*n) because we use a 2D array to store path counts for each cell

vs Alternative: Compared to recursive approach without memoization which is exponential, this DP approach is efficient and avoids repeated calculations

Edge Cases

Grid with 1 row or 1 column

Returns 1 because only one path exists (all right or all down moves)

DSA Typescript

for (let col = 0; col < n; col++) {
  dp[0][col] = 1;
}

Grid size 0 (m=0 or n=0)

Function returns 0 or no paths since grid is invalid or empty

DSA Typescript

Added explicit guard: if (m === 0 || n === 0) return 0;

When to Use This Pattern

When you see a grid and need to count paths moving only right or down, use DP to build solutions from smaller subproblems because each cell depends on top and left neighbors.

Common Mistakes

Mistake: Not initializing first row and first column with 1s
Fix: Explicitly set dp[0][col] and dp[row][0] to 1 before filling the rest of the grid

Mistake: Adding dp[row][col - 1] and dp[row - 1][col] in wrong order or indices
Fix: Ensure dp[row][col] = dp[row - 1][col] + dp[row][col - 1] to correctly sum top and left cells

Summary

Calculates the number of unique paths from top-left to bottom-right in a grid moving only right or down.

Use when counting ways to traverse grids with movement restrictions.

Each cell's paths count is the sum of paths from the cell above and the cell to the left.