Unique Paths in Grid DP in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Unique Paths Calculation

What is the output of the following TypeScript code that calculates unique paths in a 3x3 grid?

DSA Typescript

function uniquePaths(m: number, n: number): number {
  const dp: number[][] = Array(m).fill(0).map(() => Array(n).fill(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));

A 1

B 3

C 9

D 6

💡 Hint

Think about how many ways you can reach each cell by moving only right or down.

The code uses dynamic programming to fill a 3x3 grid where each cell represents the number of unique paths to reach it. The first row and column are initialized to 1 because there is only one way to reach cells in the first row (all moves right) or first column (all moves down). For other cells, the number of paths is the sum of paths from the cell above and the cell to the left. For a 3x3 grid, the total unique paths to the bottom-right corner is 6.

🧠 Conceptual

intermediate

Understanding Base Cases in Unique Paths DP

In the Unique Paths dynamic programming solution, why do we initialize the first row and first column with 1s?

A Because there is only one way to reach any cell in the first row or first column by moving only right or down.

B Because initializing with 1s reduces the time complexity to O(1).

C Because the first row and column are never visited in the path calculation.

D Because the first row and column represent obstacles that block paths.

💡 Hint

Think about how you can move from the start to cells in the first row or column.

In the grid, you can only move right or down. To reach any cell in the first row, you must move right all the way from the start, so there is only one path. Similarly, to reach any cell in the first column, you must move down all the way. Initializing these cells with 1 sets the base for calculating paths to other cells.

❓ Predict Output

advanced

Output with Obstacle Grid

What is the output of this TypeScript code that calculates unique paths in a 3x3 grid with an obstacle at position (1,1)?

DSA Typescript

function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0].length;
  const dp: number[][] = Array(m).fill(0).map(() => Array(n).fill(0));

  dp[0][0] = obstacleGrid[0][0] === 0 ? 1 : 0;

  for (let i = 1; i < m; i++) {
    dp[i][0] = (obstacleGrid[i][0] === 0 && dp[i - 1][0] === 1) ? 1 : 0;
  }

  for (let j = 1; j < n; j++) {
    dp[0][j] = (obstacleGrid[0][j] === 0 && dp[0][j - 1] === 1) ? 1 : 0;
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (obstacleGrid[i][j] === 0) {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      } else {
        dp[i][j] = 0;
      }
    }
  }

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

const grid = [
  [0,0,0],
  [0,1,0],
  [0,0,0]
];

console.log(uniquePathsWithObstacles(grid));

A 3

B 4

C 2

D 1

💡 Hint

Consider how the obstacle blocks some paths.

The obstacle at position (1,1) blocks paths that would normally pass through that cell. The dynamic programming table counts paths avoiding the obstacle. For this 3x3 grid with one obstacle, there are 2 unique paths from top-left to bottom-right.

🔧 Debug

advanced

Identify the Bug in Unique Paths Code

This TypeScript code is intended to calculate unique paths in a grid but produces incorrect output. What is the bug?

DSA Typescript

function uniquePaths(m: number, n: number): number {
  const dp: number[][] = Array(m).fill([]).map(() => Array(n).fill(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));

A Using Array(m).fill([]) causes all rows to reference the same array, leading to incorrect updates.

B The loops should start from 0 instead of 1 to include all cells.

C The dp array should be initialized with zeros instead of ones.

D The return statement should be dp[0][0] instead of dp[m - 1][n - 1].

💡 Hint

Check how the dp array is initialized and how it affects updates.

Using Array(m).fill([]) fills the array with references to the same inner array. This means updating one row updates all rows, causing incorrect path counts. The correct approach is to use map to create independent arrays for each row.

🚀 Application

expert

Number of Unique Paths in a 5x7 Grid

Using the standard Unique Paths dynamic programming approach (no obstacles), what is the number of unique paths from the top-left to bottom-right corner in a 5 rows by 7 columns grid?

A 330

B 210

C 792

D 462

💡 Hint

The number of unique paths in an m x n grid is the binomial coefficient C(m+n-2, m-1).

The number of unique paths from top-left to bottom-right in a grid of size m x n is given by the binomial coefficient C(m+n-2, m-1) or C(m+n-2, n-1). For a 5x7 grid, this is C(10,4) = 210 or C(10,6) = 210. The correct unique paths count is 210.

Practice

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

easy

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

B. The shortest path distance between two points in a grid.

C. The maximum sum path in a grid.

D. The number of obstacles in a grid.

Solution

1. Step 1: Understand the problem statement

   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: Identify the key movement constraints

   Only moves to the right or down are allowed, so the problem counts unique sequences of these moves.

3. Final Answer:

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

4. Quick Check:

   Unique paths = count of right/down moves sequences [OK]

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

Common Mistakes:

• Confusing unique paths with shortest path length
• Including diagonal moves
• Counting obstacles instead of paths

2. Which of the following TypeScript code snippets correctly initializes a 2D DP array for a grid of size m x n filled with zeros?

easy

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

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

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

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

Solution

1. Step 1: Understand how to create independent rows

   Using Array.from with a mapping function creates new arrays for each row, 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 pass an array (not a function) to .map(), causing TypeError. const dp = Array.from({ length: m }, () => Array(n).fill(0)); correctly creates independent rows filled with zeros.

3. Final Answer:

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

4. Quick Check:

   Use Array.from with a function for 2D arrays [OK]

Hint: Use Array.from with a function to avoid shared references [OK]

Common Mistakes:

• Using fill with a single array causes shared references
• Passing non-function to .map() causes TypeError
• Not initializing inner arrays separately

3. What is the output of the following TypeScript code for a 3x3 grid?

function uniquePaths(m: number, n: number): number {
  const dp = Array.from({ length: m }, () => Array(n).fill(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. 1

B. 3

C. 6

D. 9

Solution

1. Step 1: Initialize dp array with 1s

   Each cell in the first row and first column is 1, representing only one path to those cells.

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

   For each cell dp[i][j], sum dp[i-1][j] (top) and dp[i][j-1] (left). For 3x3, dp[2][2] = 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Unique paths in 3x3 grid = 6 [OK]

Hint: Sum paths from top and left cells to fill dp [OK]

Common Mistakes:

• Starting loops from 0 instead of 1
• Not initializing first row and column to 1
• Returning wrong dp cell

4. Identify the bug in this TypeScript code for unique paths and select the fix:

function uniquePaths(m: number, n: number): number {
  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];
}

medium

A. Change multiplication (*) to addition (+) in dp update.

B. Initialize dp with 1s instead of 0s.

C. Start loops from 0 instead of 1.

D. Return dp[0][0] instead of dp[m-1][n-1].

Solution

1. Step 1: Identify the dp update formula

   The code uses multiplication (*) to combine paths, which is incorrect because paths add up, not multiply.

2. Step 2: Correct the dp update to addition

   Replace dp[i - 1][j] * dp[i][j - 1] with dp[i - 1][j] + dp[i][j - 1] to sum paths from top and left.

3. Final Answer:

   Change multiplication (*) to addition (+) in dp update. -> Option A

4. Quick Check:

   Paths combine by addition, not multiplication [OK]

Hint: Sum top and left dp cells, don't multiply [OK]

Common Mistakes:

• Using multiplication instead of addition
• Incorrect dp initialization
• Wrong loop start indices

5. Given a grid with obstacles represented by 1s and empty spaces by 0s, how would you modify the unique paths DP solution to count paths avoiding obstacles?

const grid = [
  [0,0,0],
  [0,1,0],
  [0,0,0]
];

hard

A. Ignore obstacles and calculate paths normally.

B. Set dp[i][j] = 0 if grid[i][j] is 1; else dp[i][j] = dp[i-1][j] + dp[i][j-1].

C. Set dp[i][j] = 1 if grid[i][j] is 1; else 0.

D. Multiply dp[i-1][j] and dp[i][j-1] regardless of obstacles.

Solution

1. Step 1: Mark obstacle cells as unreachable

   If grid[i][j] is 1 (obstacle), set dp[i][j] = 0 to block paths through it.

2. Step 2: Calculate dp for free cells

   For cells without obstacles, dp[i][j] = dp[i-1][j] + dp[i][j-1], summing paths from top and left.

3. Final Answer:

   Set dp[i][j] = 0 if grid[i][j] is 1; else dp[i][j] = dp[i-1][j] + dp[i][j-1]. -> Option B

4. Quick Check:

   Obstacles block paths by setting dp to zero [OK]

Hint: Set dp to zero on obstacles, sum paths otherwise [OK]

Common Mistakes:

• Ignoring obstacles in dp calculation
• Setting dp to 1 on obstacles
• Multiplying paths instead of adding