Unique Paths II
Unique Paths II: count right/down paths from top-left to bottom-right on a grid with obstacle cells.
- m == obstacleGrid.length
- n == obstacleGrid[i].length
- 1 <= m, n <= 100
- obstacleGrid[i][j] is 0 or 1.
Intuition
Unique paths ii adds obstacles to the grid-path counting problem. Movement is still right or down only, but blocked cells cannot be entered.
The obstacle changes what is possible, and the combinatorial formula from the original problem breaks completely — with blocked cells, paths can no longer be counted as arrangements of moves.
The DP survives with one addition:
- A blocked cell has zero paths reaching it, so set dp[i][j] = 0 and let that zero propagate naturally to everything downstream.
That propagation is the elegance of the approach. Cells beyond an obstacle receive contributions of 0 from the blocked direction, and a fully walled-off region ends up with 0 automatically — no reachability analysis is needed anywhere.
For open cells the recurrence is unchanged: dp[i][j] = dp[i-1][j] + dp[i][j-1].
The first row and column need care, and this is where the problem differs most from the original. In Unique Paths they are all 1; here, once an obstacle appears in the first row, every cell after it is unreachable and must be 0 — there is no way around within that row.
Setting the entire first row to 1 without checking for obstacles is the standard bug, and it inflates the count on any input with an edge obstacle.
Two boundary cases decide the answer immediately. If the start or the destination is blocked, the answer is 0 — no path can begin or end there.
The grid can be modified in place for O(1) extra space, or collapsed to a single row for O(n).
Every cell is computed once, giving O(m × n) time.
Grid DP where an obstacle forces the cell to zero — it contributes no paths onward. Everything else is the standard top + left sum. Zeroing rather than skipping is what propagates the blockage correctly through the rest of the grid.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(R*C) time and O(R*C), reducible to O(C) with a rolling row space.
Note that the formula breaks
Obstacles invalidate the combinatorial argument entirely — paths are no longer arrangements of moves, so only the DP works here.
Check the endpoints first
If the start or destination is blocked, return 0. No path can begin or end at an obstacle, and this settles the input immediately.
Zero out blocked cells
Set dp[i][j] = 0 at every obstacle. That zero propagates downstream automatically, so no reachability analysis is needed.
Keep the open-cell recurrence
dp[i][j] = dp[i-1][j] + dp[i][j-1] for passable cells — unchanged from the original problem.
Stop the first row at an obstacle
Once an obstacle appears in the first row, every later cell is 0 — there is no way around within that row. Setting them all to 1 inflates the count.
Apply the same rule to the first column
The first column behaves identically: cells after an obstacle are unreachable and must be zero.
Cost of the tabulation
Every cell is computed once, giving O(m × n) time, with O(1) space when modifying the grid in place.
Solution & live demo
Common pitfalls
Skipping obstacle cells instead of zeroing them
if obstacleGrid[i][j] == 1:
continueif obstacleGrid[i][j] == 1:
dp[i][j] = 0
continueIn a freshly allocated array continue happens to leave 0, but on a reused or pre-seeded row it leaves a stale count that leaks paths through the wall. Setting it explicitly states the invariant.
Seeding the first row and column unconditionally
for j in range(C): dp[0][j] = 1
top = dp[i-1][j] if i > 0 else 0 left = dp[i][j-1] if j > 0 else 0
An obstacle in the first row blocks every cell after it, so the row isn't all 1s. Letting the general recurrence handle the edges — with 0 for out-of-range neighbours — gets it right automatically.
Not checking the start cell
dp[0][0] = 1
if obstacleGrid[0][0] == 1:
return 0If the starting square is blocked there are no paths at all, but seeding it to 1 manufactures one and propagates it through the entire grid.
Edge cases
Return 0 immediately, since a path needs a first step that doesn't exist.
Every cell after it in that row inherits dp = 0 from the top contribution being 0 and the left contribution chaining through the blocked cell.
dp[R-1][C-1] is forced to 0 during the fill, correctly reporting no valid path.
dp[0][0] = 1 and that is also the destination, so the answer is 1 with no fill loop needed.