Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Two-Dimensional DP

Guide 2 of 6 · Path 2 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtwo-dimensional-dp

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

1D DP with obstacles zeroed

Tested only
Time O(mn)Space O(n)

Idea. Rolling row dp[c]: if obstacle set 0; else dp[c] += dp[c-1] (left). Top/left blocked via zeros.

Walkthrough. [[0,0,0],[0,1,0],[0,0,0]] → 2 paths around the center obstacle.

Trade-offs. Guard start/end obstacles early for a clean 0 return.

Solution
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