Unique Paths II

Problem (restated)

Robot from top-left to bottom-right (right/down only) on a grid with obstacles (1). Count paths; 0 if blocked.

Intuition

Same as Unique Paths, but an obstacle cell has 0 ways and does not propagate.

Approaches

export function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0]!.length;
  if (obstacleGrid[0]![0] === 1 || obstacleGrid[m - 1]![n - 1] === 1) return 0;
  const dp = Array(n).fill(0);
  dp[0] = 1;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (obstacleGrid[r]![c] === 1) {
        dp[c] = 0;
      } else if (c > 0) {
        dp[c] += dp[c - 1]!;
      }
    }
  }
  return dp[n - 1]!;
}

export function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0]!.length;
  if (obstacleGrid[0]![0] === 1 || obstacleGrid[m - 1]![n - 1] === 1) return 0;
  const dp = Array(n).fill(0);
  dp[0] = 1;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (obstacleGrid[r]![c] === 1) {
        dp[c] = 0;
      } else if (c > 0) {
        dp[c] += dp[c - 1]!;
      }
    }
  }
  return dp[n - 1]!;
}

Template connection

Grid path DP with blocked cells.

Reflection

• Keep one row. An obstacle writes 0. Any other cell adds the left neighbor onto the value already stored from above. After the first obstacle, the rest of the first row stays 0.
• A blocked start or a blocked finish answers 0. With no obstacles the grid matches unique paths.
• A single open cell is 1. A single blocked cell is 0.