Unique Paths in Grid DP in DSA Javascript

Mental Model

Count how many ways you can move from the top-left corner to the bottom-right corner of a grid by only moving right or down.

Analogy: Imagine walking through a city grid where you can only go east or south to reach your destination. You want to know how many different routes you can take without backtracking.

Start (S) at top-left, End (E) at bottom-right in a 3x3 grid:
S -> _ -> _
↓    ↓    ↓
_ -> _ -> _
↓    ↓    ↓
_ -> _ -> E

Dry Run Walkthrough

Input: Grid size: 3 rows x 3 columns

Goal: Find the number of unique paths from top-left to bottom-right moving only right or down

Step 1: Initialize a 3x3 grid with 1s in the first row and first column

[1] -> [1] -> [1]
 ↑     ↑     ↑
[1] -> [ ] -> [ ]
 ↑     ↑     ↑
[1] -> [ ] -> [ ]

Why: There is only 1 way to reach any cell in the first row (all rights) or first column (all downs)

Step 2: Calculate paths for cell (1,1) by adding paths 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 3: Calculate paths for cell (1,2) by adding paths 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 4: Calculate paths for cell (2,1) by adding paths 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 5: Calculate paths for cell (2,2) by adding paths 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]
Answer: 6 unique paths

Annotated Code

DSA Javascript

class UniquePaths {
  constructor(m, n) {
    this.m = m;
    this.n = n;
    this.dp = Array.from({ length: m }, () => Array(n).fill(0));
  }

  countPaths() {
    // Initialize first row and first column with 1
    for (let i = 0; i < this.m; i++) {
      this.dp[i][0] = 1; // only one way down
    }
    for (let j = 0; j < this.n; j++) {
      this.dp[0][j] = 1; // only one way right
    }

    // Fill the dp table
    for (let i = 1; i < this.m; i++) {
      for (let j = 1; j < this.n; j++) {
        this.dp[i][j] = this.dp[i - 1][j] + this.dp[i][j - 1]; // sum of top and left
      }
    }

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

// Driver code
const gridRows = 3;
const gridCols = 3;
const uniquePaths = new UniquePaths(gridRows, gridCols);
const result = uniquePaths.countPaths();

// Print dp grid
for (let i = 0; i < gridRows; i++) {
  console.log(uniquePaths.dp[i].join(' -> '));
}
console.log('Answer:', result);

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

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

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

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

this.dp[i][j] = this.dp[i - 1][j] + this.dp[i][j - 1];

Calculate paths to current cell by summing paths from top and left cells

Output

1 -> 1 -> 1

1 -> 2 -> 3

1 -> 3 -> 6

Answer: 6

Complexity Analysis

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

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

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

The number of unique paths is 1 because you can only move straight right or down

DSA Javascript

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

Grid size 0 (no rows or columns)

Returns 0 or no paths since grid is invalid

DSA Javascript

Not explicitly handled; would require input validation before creating dp array

When to Use This Pattern

When asked to count ways to reach a point in a grid with restricted moves, use dynamic programming to build solutions from smaller subproblems.

Common Mistakes

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

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

Summary

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

Use when you need to count distinct routes in a grid with movement constraints.

The key insight is that paths to a cell equal the sum of paths to the cell above and to the left.

Practice

1. What does the problem Unique Paths in Grid DP ask you to find?

easy

A. The number of different ways to move from the top-left to bottom-right corner of a grid using only right and down moves.

B. The shortest path length from top-left to bottom-right in a grid.

C. The maximum sum path from top-left to bottom-right in a grid.

D. The number of obstacles in the grid.

Solution

1. Step 1: Understand the problem goal

   The problem asks for counting all possible paths from the top-left corner to the bottom-right corner of a grid, moving only right or down.

2. Step 2: Differentiate from other path problems

   It is not about shortest path length, maximum sum, or obstacles count, but about counting unique paths.

3. Final Answer:

   The number of different ways to move from the top-left to bottom-right corner of a grid using only right and down moves. -> Option A

4. Quick Check:

   Unique paths count = number of ways to move right/down [OK]

Hint: Count paths by moving only right or down [OK]

Common Mistakes:

• Confusing unique paths with shortest path length
• Thinking about obstacles when none are given
• Counting diagonal moves

2. Which of the following JavaScript code snippets correctly initializes a 2D array dp of size m x n filled with zeros for the Unique Paths problem?

easy

A. const dp = Array.from({ length: m }, () => Array(n).fill(0));

B. const dp = Array(m).fill(Array(n).fill(0));

C. const dp = new Array(m).map(() => new Array(n));

D. const dp = Array(m).map(() => Array(n));

Solution

1. Step 1: Understand array initialization in JavaScript

   Using Array.from with a mapping function creates independent inner arrays, avoiding shared references.

2. Step 2: Analyze each option

   const dp = Array(m).fill(Array(n).fill(0)); shares the same inner array reference for all rows, causing bugs. Options C and D create inner arrays with undefined elements instead of zeros (missing .fill(0)). const dp = Array.from({ length: m }, () => Array(n).fill(0)); correctly creates independent arrays filled with zeros.

3. Final Answer:

   const dp = Array.from({ length: m }, () => Array(n).fill(0)); -> Option A

4. Quick Check:

   Use Array.from with arrow function for 2D array [OK]

Hint: Use Array.from with function to avoid shared inner arrays [OK]

Common Mistakes:

• Using fill with array directly causing shared references
• Not filling inner arrays with zeros (elements undefined)
• Not initializing inner arrays separately

3. What is the output of the following JavaScript code for uniquePaths(3, 3)?

function uniquePaths(m, n) {
  const dp = Array.from({ length: m }, () => Array(n).fill(0));
  for (let i = 0; i < m; i++) dp[i][0] = 1;
  for (let j = 0; j < n; j++) dp[0][j] = 1;
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m - 1][n - 1];
}
console.log(uniquePaths(3, 3));

medium

A. 3

B. 6

C. 9

D. 12

Solution

1. Step 1: Initialize dp array and base cases

   Set first row and first column to 1 because only one way to reach cells in first row or column.

2. Step 2: Fill dp using sum of top and left cells

   Calculate dp[1][1] = 1+1=2, dp[1][2] = 1+2=3, dp[2][1] = 2+1=3, dp[2][2] = 3+3=6.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Unique paths in 3x3 grid = 6 [OK]

Hint: Sum paths from top and left neighbors [OK]

Common Mistakes:

• Not initializing first row and column to 1
• Adding instead of summing dp[i-1][j] and dp[i][j-1]
• Off-by-one errors in loops

4. The following code attempts to solve the Unique Paths problem but overwrites values across multiple rows unexpectedly for uniquePaths(3, 3). What is the bug?

function uniquePaths(m, n) {
  const dp = Array(m).fill(Array(n).fill(0));
  for (let i = 0; i < m; i++) dp[i][0] = 1;
  for (let j = 0; j < n; j++) dp[0][j] = 1;
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m - 1][n - 1];
}

medium

A. The dp array is not initialized with zeros.

B. The loops start from 1 instead of 0.

C. Using fill with array causes all rows to reference the same array.

D. The return statement is outside the function.

Solution

1. Step 1: Analyze dp initialization

   Using Array(m).fill(Array(n).fill(0)) makes all rows point to the same inner array, so updating one row updates all rows.

2. Step 2: Understand effect on dp updates

   Setting dp[i][0] = 1 changes the same array for all rows. During table filling, updates overwrite values from earlier rows (e.g., dp[1][1] becomes 3 instead of 2), causing incorrect intermediate values.

3. Final Answer:

   Using fill with array causes all rows to reference the same array. -> Option C

4. Quick Check:

   Shared references cause wrong dp updates [OK]

Hint: Avoid fill with array; use Array.from for independent rows [OK]

Common Mistakes:

• Using fill with array causing shared references
• Incorrect loop ranges
• Misplaced return statement

5. Given a grid with obstacles represented by a 2D array obstacleGrid where 1 means obstacle and 0 means free cell, how would you modify the Unique Paths DP solution to count unique paths avoiding obstacles?

hard

A. Set dp[i][j] = 1 for all cells without checking obstacles.

B. Ignore obstacles and calculate paths as usual.

C. Use recursion without memoization to count paths.

D. Initialize dp with zeros, set dp[0][0] = 1 if no obstacle, then for each cell dp[i][j] = 0 if obstacle else dp[i-1][j] + dp[i][j-1].

Solution

1. Step 1: Initialize dp considering obstacles

   Set dp[0][0] to 1 only if the start cell has no obstacle; otherwise 0.

2. Step 2: Update dp cells with obstacle check

   For each cell, if obstacleGrid[i][j] is 1, dp[i][j] = 0 (no path). Else dp[i][j] = dp[i-1][j] + dp[i][j-1].

3. Step 3: Return dp[m-1][n-1]

   This gives the count of unique paths avoiding obstacles.

4. Final Answer:

   Initialize dp with zeros, set dp[0][0] = 1 if no obstacle, then for each cell dp[i][j] = 0 if obstacle else dp[i-1][j] + dp[i][j-1]. -> Option D

5. Quick Check:

   Obstacle cells block paths by setting dp to 0 [OK]

Hint: Set dp=0 for obstacles, sum paths only for free cells [OK]

Common Mistakes:

• Ignoring obstacles in dp calculation
• Not initializing start cell properly
• Using recursion without memoization causing inefficiency