Unique Paths II
Count right/down paths from top-left to bottom-right on a grid with obstacle cells.
Open on LeetCode ↗Intuition
Plain Unique Paths seeds the entire first row and first column with 1s before filling the interior. Copy that habit here and it silently produces wrong answers: an obstacle in the first row or column blocks everything BEHIND it too, since a path can't walk through it to reach cells further along that row or column. The seeding has to stop dead at the first obstacle, not run to the edge assuming a clear line. There's also a degenerate case the seeding trick hides: if the start cell itself is an obstacle, the answer is 0 immediately, no DP required.
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
Handle a blocked start
If grid[0][0] is 1, no path can even begin; return 0 immediately without building a DP table.
Fill with obstacle-aware transitions
Build dp the same shape as grid. Set dp[0][0] = 1. For every other cell, if it's an obstacle set dp[cell] = 0 outright. Otherwise sum the ways in from above and from the left, treating an out-of-bounds or obstacle neighbor as contributing 0. Because an obstacle's dp value is forced to 0, that 0 naturally propagates forward and stops the first row or column from continuing past it, without special-casing row 0 or column 0 separately.
Read the bottom-right corner
dp[R-1][C-1] holds the total path count avoiding every obstacle; if that cell is itself an obstacle it will correctly be 0.
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.