Unique Paths in Grid DP in DSA Javascript - Deep Dive

Overview - Unique Paths in Grid DP

What is it?

Unique Paths in Grid DP is a way to count how many different ways you can move from the top-left corner to the bottom-right corner of a grid, moving only right or down. It uses a method called dynamic programming to remember past results so it doesn't repeat work. This helps solve problems where you want to find the number of possible routes in a grid efficiently. The grid can be thought of as a map with rows and columns.

Why it matters

Without this method, counting all possible paths would take a very long time because the number of paths grows very fast as the grid gets bigger. This would make many problems too slow to solve. Using dynamic programming to find unique paths helps computers solve these problems quickly, which is important in areas like robotics, games, and navigation systems. It shows how breaking a big problem into smaller parts saves time and effort.

Where it fits

Before learning this, you should understand basic loops, arrays, and simple recursion. After this, you can learn more complex dynamic programming problems like those with obstacles or variable moves, and then move on to graph algorithms and pathfinding techniques.

Mental Model

Core Idea

Count the ways to reach each cell by adding the ways to reach the cell above and the cell to the left, building up from the start.

Think of it like...

Imagine walking through a city grid where you can only move east or south. To get to any intersection, you can come from the intersection above or the one to the left. The total ways to get there is the sum of ways to get to those two intersections.

Start (0,0)
  ↓       ->
(0,0) -> (0,1) -> (0,2) -> ...
  ↓       ↓       ↓
(1,0) -> (1,1) -> (1,2) -> ...
  ↓       ↓       ↓
 ...     ...     ...
Each cell = ways from above + ways from left

Build-Up - 7 Steps

1

Foundation

Understanding the Grid and Moves

Concept: Introduce the grid layout and allowed moves (right and down).

Imagine a grid with rows and columns. You start at the top-left corner (row 0, column 0). You can only move either one step to the right or one step down at a time. The goal is to reach the bottom-right corner. This sets the stage for counting paths.

Result

You know the problem space: a grid and two possible moves at each step.

Understanding the movement rules is essential because it limits the paths and makes counting possible.

2

Foundation

Brute Force Counting of Paths

Concept: Count all paths by exploring every possible move recursively.

Start at the top-left cell. From each cell, try moving right and down recursively until you reach the bottom-right cell. Count each successful path. This method works but repeats many calculations and is slow for big grids.

Result

You get the total number of paths but with many repeated steps and slow performance.

Seeing the brute force method shows why we need a better way to avoid repeating work.

3

Intermediate

Dynamic Programming Table Setup

Concept: Use a table to store the number of ways to reach each cell.

Create a 2D array the same size as the grid. Initialize the first row and first column with 1 because there's only one way to reach cells in the first row (all right moves) or first column (all down moves). This table will store the count of unique paths to each cell.

Result

A table with base cases filled, ready to build the solution.

Setting base cases correctly is crucial because they anchor the rest of the calculations.

4

Intermediate

Filling the DP Table with Recurrence

🤔Before reading on: do you think the number of ways to reach a cell depends on one or two neighboring cells? Commit to your answer.

Concept: Calculate each cell's value by adding the values from the cell above and the cell to the left.

For each cell not in the first row or column, the number of ways to get there equals the sum of ways to get to the cell above plus the ways to get to the cell on the left. This is because you can only come from those two directions.

Result

A fully filled table where the bottom-right cell contains the total unique paths.

Understanding this addition rule is the heart of the dynamic programming solution.

5

Intermediate

Implementing the DP Solution in Code

🤔Before reading on: do you think the DP solution requires recursion or iteration? Commit to your answer.

Concept: Translate the DP logic into a simple iterative code using loops.

Use nested loops to fill the DP table row by row or column by column. Initialize the first row and column with 1s. Then for each cell, set dp[i][j] = dp[i-1][j] + dp[i][j-1]. Finally, return dp[m-1][n-1] as the answer.

Result

Code that efficiently computes the number of unique paths in O(m*n) time.

Knowing how to implement DP iteratively avoids stack overhead and is easier to debug.

6

Advanced

Optimizing Space Usage in DP

🤔Before reading on: do you think we need to store the entire DP table or just part of it? Commit to your answer.

Concept: Reduce memory by using a single array to store the current row's path counts.

Since each dp[i][j] depends only on dp[i-1][j] (previous row) and dp[i][j-1] (current row left), we can use a 1D array. Update the array as you move through rows, adding the value from the left to the current cell. This reduces space from O(m*n) to O(n).

Result

A memory-efficient solution that still runs in O(m*n) time.

Understanding dependencies lets you optimize space without losing correctness.

7

Expert

Handling Obstacles and Variations

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

Concept: Extend the DP method to grids with obstacles where some cells cannot be passed.

Modify the DP table so that if a cell has an obstacle, set its ways to 0. For other cells, sum ways from above and left only if those cells are reachable. This requires checking obstacles during DP filling. This approach generalizes the unique paths problem.

Result

A robust DP solution that counts paths avoiding obstacles.

Adapting DP to constraints shows its flexibility and real-world applicability.

Under the Hood

The DP solution builds a table where each cell stores the count of unique paths to reach it. It uses the fact that to get to a cell, you must come from either the cell above or the cell to the left. By storing these counts, the algorithm avoids recalculating paths multiple times, which happens in naive recursion. Internally, this is a bottom-up approach filling a matrix with cumulative counts.

Why designed this way?

Dynamic programming was designed to solve problems with overlapping subproblems and optimal substructure efficiently. Unique Paths fits this because the number of ways to reach a cell depends only on smaller subproblems (cells above and left). Alternatives like pure recursion are too slow due to repeated calculations. DP trades extra memory for speed.

┌─────────────┐
│ Start (0,0) │
└─────┬───────┘
      │
┌─────▼───────┐
│ DP Table    │
│ +---------+ │
│ | 1 1 1 1 | │
│ | 1 2 3 4 | │
│ | 1 3 6 10| │
│ +---------+ │
└─────┬───────┘
      │
┌─────▼───────┐
│ Result: 10  │
└─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Do you think the number of unique paths grows linearly with grid size? Commit to yes or no.

Common Belief: The number of unique paths increases linearly as the grid gets bigger.

Reality: The number of unique paths grows combinatorially, much faster than linear growth.

Why it matters: Underestimating growth leads to inefficient algorithms that can't handle large grids.

Quick: Do you think you can move diagonally in the Unique Paths problem? Commit to yes or no.

Common Belief: You can move diagonally as well as right and down.

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

Why it matters: Allowing diagonal moves changes the problem and the counting method, leading to wrong answers.

Quick: Do you think the DP table stores the actual paths? Commit to yes or no.

Common Belief: The DP table stores the actual paths taken to reach each cell.

Reality: The DP table stores only the count of unique paths, not the paths themselves.

Why it matters: Confusing counts with paths can cause misunderstanding of what DP solves and how to reconstruct paths if needed.

Quick: Do you think the DP solution always requires a 2D array? Commit to yes or no.

Common Belief: You must always use a 2D array to solve Unique Paths with DP.

Reality: You can optimize space by using a 1D array because each cell depends only on the current and previous row.

Why it matters: Not knowing space optimization can lead to unnecessary memory use in large problems.

Expert Zone

1

The order of filling the DP table matters; filling row-wise or column-wise works because dependencies are only from top and left.

2

When optimizing space, careful updating of the 1D array is needed to avoid overwriting values before they are used.

3

In grids with obstacles, early detection of unreachable cells can prune computations and improve performance.

When NOT to use

This DP approach is not suitable if moves other than right and down are allowed, or if the grid is very large and memory is limited. In such cases, combinatorial formulas or probabilistic methods might be better.

Production Patterns

In real systems, this DP pattern is used in robot path planning, game level design for counting routes, and network routing algorithms where constraints are similar. Often combined with obstacle handling and path reconstruction.

Connections

Pascal's Triangle

The DP table values correspond to binomial coefficients found in Pascal's Triangle.

Recognizing this connection allows using combinatorial formulas to compute unique paths without DP.

Memoization in Recursion

DP is a bottom-up version of memoized recursion solving the same overlapping subproblems.

Understanding memoization helps grasp why DP avoids repeated calculations by storing intermediate results.

Combinatorics in Mathematics

Counting unique paths is a combinatorial problem of choosing steps in sequences.

Knowing combinatorics provides a direct formula for unique paths, linking math and programming.

Common Pitfalls

#1 Initializing the first row and column incorrectly.

Wrong approach:

for(let i=0; i

Correct approach:

for(let i=0; i

Root cause:

Not setting base cases means the DP table has zeros, so sums remain zero and the final count is wrong.

#2 Using recursion without memoization for large grids.

Wrong approach:

function countPaths(i, j) {
if(i == m-1 && j == n-1) return 1;
if(i >= m || j >= n) return 0;
return countPaths(i+1, j) + countPaths(i, j+1);
}

Correct approach:

Use a DP table or memo object to store results of countPaths(i,j) to avoid repeated calls.

Root cause:

Pure recursion repeats calculations exponentially, causing slow performance or stack overflow.

#3 Confusing the problem by allowing diagonal moves.

Wrong approach:

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

Correct approach:

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

Root cause:

Adding diagonal moves changes the problem and the recurrence relation, leading to incorrect counts.

Key Takeaways

Unique Paths in Grid DP counts the number of ways to reach the bottom-right cell by moving only right or down.

Dynamic programming solves this efficiently by building a table of path counts using results from smaller subproblems.

Base cases for the first row and column are essential because they represent paths with only one direction.

Space can be optimized from a 2D table to a 1D array by understanding dependencies between cells.

The problem connects deeply with combinatorics and can be extended to handle obstacles and other constraints.

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