Unique Paths in Grid DP in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the DP array with zeros.

DSA Typescript

const dp: number[][] = Array(m).fill(0).map(() => Array(n).fill([1]));

Drag options to blanks, or click blank then click option'

Aundefined

B1

Cnull

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 instead of 0 initializes paths incorrectly.

Using null or undefined causes runtime errors.

We fill the DP array with zeros to start counting paths from zero.

2fill in blank

medium

Complete the code to set the starting point paths count to 1.

DSA Typescript

dp[0][0] = [1];

Drag options to blanks, or click blank then click option'

A1

B0

C-1

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Setting starting point to 0 means no paths start there.

Using negative or null values causes errors.

The starting cell has exactly one path to itself.

3fill in blank

hard

Fix the error in the nested loops to correctly iterate over the grid.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

Am

Bn

Cdp.length

Ddp[0].length

Attempts:

3 left

💡 Hint

Common Mistakes

Using n in outer loop causes index errors.

Using dp.length or dp[0].length may confuse rows and columns.

The outer loop should run from 0 to m (rows).

4fill in blank

hard

Fill both blanks to correctly return the total unique paths from top-left to bottom-right.

DSA Typescript

return dp[[1] - 1][[2] - 1];

Drag options to blanks, or click blank then click option'

Am

Bn

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or 1 as indices returns wrong cell.

Swapping m and n causes wrong indexing.

The bottom-right cell is at index m-1, n-1 in the DP array.

5fill in blank

hard

Fill all three blanks to complete the function that calculates unique paths in an m x n grid.

DSA Typescript

function uniquePaths([1]: number, [2]: number): number {
  const dp: number[][] = Array([1]).fill(0).map(() => Array([2]).fill(0));
  dp[0][0] = 1;
  for (let i = 0; i < [1]; i++) {
    for (let j = 0; j < [2]; j++) {
      if (i === 0 && j === 0) continue;
      dp[i][j] = (i > 0 ? dp[i - 1][j] : 0) + (j > 0 ? dp[i][j - 1] : 0);
    }
  }
  return dp[[1] - 1][[2] - 1];
}

Drag options to blanks, or click blank then click option'

Am

Bn

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up m and n in parameters and array dimensions.

Using inconsistent variable names causes errors.

The function parameters and DP array dimensions use m and n consistently.

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