Unique Paths II
Count right-and-down paths through a grid with obstacles using DP: an obstacle holds 0 paths, every open cell adds the paths from above and from the left.
Problem Understanding
Unique Paths II: a robot starts at the top-left of an m × n grid and moves only right or down to the bottom-right. Some cells are obstacles (1) that it cannot enter. Return the number of distinct paths.
Example: [[0,0,0],[0,1,0],[0,0,0]] returns 2: around the obstacle on the top or on the left.
The Intuition: Obstacles Hold Zero
Without obstacles, this is Unique Paths: the paths into a cell are the paths into the cell above plus the paths into the cell to the left.
Obstacles need one extra rule: an obstacle holds 0 paths. Nothing passes through it, so it adds nothing to its neighbours, and the counts route themselves around it.
- Obstacle → 0.
- Start (if open) → 1.
- Any other open cell → above + left, where a missing neighbour counts as 0.
The same grid with costs instead of counts is Minimum Path Sum.
Interactive Walkthrough
Obstacles are red and hold 0. Each open cell shows its path count once filled, and the two cells it adds are tinted. Try Two gaps to see the counts route around a wall.
Dry Run Table
Input: [[0,0,0],[0,1,0],[0,0,0]]
| dp | col 0 | col 1 | col 2 |
|---|---|---|---|
| row 0 | 1 | 1 | 1 |
| row 1 | 1 | 0 (obstacle) | 1 |
| row 2 | 1 | 1 | 2 |
dp[2][1] = 0 + 1 = 1 and dp[2][2] = 1 + 1 = 2. Answer: 2.
The Solution Template
One pass over the grid. C++ and C store counts as 64-bit integers, since intermediate cells can exceed 32 bits even when the answer fits.
Unique Paths II Code
1var uniquePathsWithObstacles = function(obstacleGrid) {2 const m = obstacleGrid.length, n = obstacleGrid[0].length;3 const dp = Array.from({ length: m }, () => new Array(n).fill(0));4 for (let i = 0; i < m; i++) {5 for (let j = 0; j < n; j++) {6 if (obstacleGrid[i][j] === 1) dp[i][j] = 0;7 else if (i === 0 && j === 0) dp[i][j] = 1;8 else dp[i][j] = (i > 0 ? dp[i - 1][j] : 0) + (j > 0 ? dp[i][j - 1] : 0);9 }10 }11 return dp[m - 1][n - 1];12};
Edge Cases & Common Mistakes
- Obstacle on the start or the end: the answer is 0; checking the obstacle first covers both.
- Filling the first row with 1s: wrong once an obstacle appears in it; every cell after it in that row is unreachable.
- Skipping obstacles instead of zeroing them: leaves stale values that neighbours then add.
- Overflow: intermediate counts can exceed 32 bits on large grids even when the final answer fits; use 64-bit cells where needed.
- One cell:
[[0]]has 1 path,[[1]]has 0.
Summary
Fill the grid row by row: obstacles hold 0 paths, the open start holds 1, and every other open cell adds the paths from above and from the left. The bottom-right cell is the answer. O(m · n) time, O(m · n) or O(n) space.
More practice: DSA interview questions with answers · patterns cheat sheet