Unique paths with obstacles
easyRight and down only, so the ways to reach a cell are the ways to reach the cell above plus the one to its left. An obstacle is just a zero - no branching logic needed.
O(rows × cols)Space O(rows × cols), or O(cols) with one rowSaved in this browser - no sign-up, nothing sent anywhere.
How unique paths with obstacles works
Moving only right and down, there are exactly two ways to arrive at any cell: from above, or from the left. So the number of routes reaching (r, c) is dp[r-1][c] + dp[r][c-1], seeded by one route to the start - being there. Counting problems reduce to sums where optimisation problems use max or min; the table mechanics are otherwise identical.
An obstacle needs no special logic: set its cell to 0 and it contributes no routes to anything downstream, which silently erases every path through it. Filling row by row guarantees the two cells each sum reads are already final. An empty R by C grid has the closed form C(R+C-2, R-1) - a 3 by 3 grid has C(4, 2) = 6 routes - and obstacles are precisely what destroy that formula and make the table necessary.
The counts grow fast - the module's default 5 by 6 grid would have C(9, 4) = 126 routes if empty - so enumerating paths one at a time is hopeless even at toy sizes. The table costs one addition per cell, rows × cols in total, and the same sweep extends directly to minimum path sum and its relatives by swapping the plus for a min.
Step by step
- Take a 3 by 3 grid with one obstacle in the centre. dp[0][0] = 1 - one way to stand at the start.
- The top row and left column fill with 1s: a single straight-line route reaches each of those cells.
- The centre cell is blocked. Write 0 - no route may pass through, and that zero will speak for it from now on.
- Cell (1, 2): 1 route arrives from above, 0 from the blocked left neighbour - 1 in total. Cell (2, 1) mirrors it.
- The corner (2, 2) sums 1 from above and 1 from the left: 2 routes survive the obstacle.
- Without the obstacle the count would be C(4, 2) = 6 - that single blocked cell removed four of the six paths.
Complexity
| Worst case time | O(rows × cols) |
|---|---|
| Space | O(rows × cols), or O(cols) with one row |
Without obstacles the answer is the binomial coefficient C(R+C−2, R−1).
Reference implementation
Python
def unique_paths(grid):
"""Count routes from the top-left to the bottom-right
moving only right and down. 1 marks an obstacle."""
rows, cols = len(grid), len(grid[0])
dp = [[0] * cols for _ in range(rows)]
dp[0][0] = 0 if grid[0][0] else 1
for r in range(rows):
for c in range(cols):
if grid[r][c]:
dp[r][c] = 0
continue
if r: dp[r][c] += dp[r - 1][c]
if c: dp[r][c] += dp[r][c - 1]
return dp[-1][-1]JavaScript
function uniquePaths(grid) {
const R = grid.length, C = grid[0].length;
const dp = Array.from({ length: R }, () => new Array(C).fill(0));
dp[0][0] = grid[0][0] ? 0 : 1;
for (let r = 0; r < R; r++)
for (let c = 0; c < C; c++) {
if (grid[r][c]) { dp[r][c] = 0; continue; }
if (r) dp[r][c] += dp[r - 1][c];
if (c) dp[r][c] += dp[r][c - 1];
}
return dp[R - 1][C - 1];
}Worth noticing
Every cell is reached from exactly two directions
Right and down only, so the number of ways to reach (r, c) is the ways to reach the cell above plus the ways to reach the cell to its left. Counting problems often reduce to a sum like this.
An obstacle is a zero, not a special case
Setting a blocked cell to 0 makes it contribute nothing to its neighbours, which automatically removes every path through it. No branching logic needed.
Without obstacles it is a binomial coefficient
An empty R×C grid has C(R+C−2, R−1) paths - the number of ways to arrange the downs among the total moves. Obstacles destroy that closed form, which is exactly when the DP earns its keep.
Common pitfalls
- Seeding dp[0][0] = 1 without checking the start for an obstacle. A blocked start - or a blocked goal - means zero paths, not one.
- Pre-filling the first row and column with 1s. An obstacle in row 0 must zero out everything after it, which the plain sum handles and the shortcut does not.
- Allowing diagonal arrivals. This count is for right and down only; adding dp[r-1][c-1] counts a move the problem never permits.
- Overflowing the counter. Path counts grow binomially - an obstacle-free 20 by 20 grid already has C(38, 19), nearly 17.7 billion routes, past 32-bit range.
Where it is used
- Robot motion planning toy models and the LeetCode 62 and 63 pair, a standard first grid DP.
- Lattice-path combinatorics - the table verifies binomial identities cell by cell when the grid is open.
- The template for minimum path sum, dungeon game and other grid DPs - same sweep, different operator.
- Counting monotonic lattice walks, the same walks that underlie alignment tables like edit distance.
Frequently asked questions
What is the time and space complexity of counting unique grid paths?
Time is O(rows × cols) - one addition per cell. Space is O(rows × cols) for the visible table, or O(cols) with a single row updated in place, since each cell reads only the current and previous rows. The default 5 by 6 grid costs 30 cells either way.
How many paths does a grid have without obstacles?
C(R+C-2, R-1): a route makes R - 1 down moves and C - 1 right moves, and choosing where the downs sit among all R+C-2 moves determines everything. A 3 by 3 grid gives C(4, 2) = 6. Obstacles break the formula - which is when the table earns its keep.
Why is an obstacle just a zero in the table?
The recurrence only ever adds a cell's value into its right and down neighbours. A cell holding 0 contributes no routes anywhere, so every path through it vanishes from the totals automatically - no branching, no special cases, exactly as if those routes never existed.
How do I reduce the space to one row?
Keep a single array indexed by column. Sweeping each row left to right, dp[c] still holds the count from the row above - add dp[c-1] into it for the routes arriving from the left, and reset blocked cells to 0. That is the O(cols) version.