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.