Algorithm

Unique Paths II

Dynamic Programming Pattern

Unique Paths II

You are given an m × n grid where each cell holds 0 for an empty square or 1 for an obstacle. A robot starts at the top-left cell and wants to reach the bottom-right cell, moving only right or down and never entering an obstacle. Return the number of distinct paths. If the start or the destination is itself an obstacle, the answer is 0.

CONSTRAINTS
  • 1 ≤ m, n ≤ 100
  • Each cell is 0 (empty) or 1 (obstacle)
  • Movement is restricted to right and down only
  • The answer fits in a signed 32-bit integer
EXAMPLE 1
Input: grid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
One route goes right, right, then down twice; the other goes down twice then right twice. Every other route would have to pass through the blocked centre cell.
EXAMPLE 2
Input: grid = [[0,1],[0,0]]
Output: 1
The cell to the right of the start is blocked, so the only legal route is down and then right.
EXAMPLE 3
Input: grid = [[1,0],[0,0]]
Output: 0
The starting cell is itself an obstacle, so the robot cannot even begin and no path exists.
EXAMPLE 4
Input: grid = [[0,0],[0,1]]
Output: 0
The destination is blocked. Routes may exist elsewhere in the grid, but none can finish, so the count is zero.
EXAMPLE 5
Input: grid = [[0,0,0],[1,1,0],[0,0,0]]
Output: 1
The wall across the middle leaves only the rightmost column open, so the robot must travel right along the top row before descending.
What if the starting cell or the destination is an obstacle?
The answer is 0 in both cases. It is worth checking explicitly at the top, because a blocked start is easy to mishandle — a base case that returns 1 for the starting cell will return 1 even when that cell is a wall unless the obstacle test comes first.
Does 1 mean an obstacle or a walkable cell?
1 is an obstacle and 0 is empty, which is the reverse of what many people assume. Getting it backwards produces a solution that is perfectly structured and completely wrong, so confirm it before writing anything.
Can the robot move around an obstacle by going up or left?
No, movement is still right and down only. That is why an obstacle in the top row makes the entire rest of that row unreachable — there is no way to come at it from another direction.
Is it possible for there to be no path at all?
Yes, and the correct response is to return 0 rather than to signal an error. The table produces that naturally, since blocked cells contribute nothing to their neighbours.
The rules

A robot moves right or down through a grid, from top-left to bottom-right, counting the routes — but now some cells are blocked. The robot may not stand on a blocked cell, so no path may pass through one.

With obstacles there is no clever counting shortcut: whether a route is legal depends on exactly where the walls sit, so you cannot count routes without looking at the grid. The table, though, barely changes. That is a handy property of these tables — a new constraint usually just forbids some cells rather than reshaping the recurrence.

The recurrence

To be standing on a walkable cell (r, c), the robot's last move came from above or from the left. So the count is the sum of those two neighbours.

The only new rule: if (r, c) is an obstacle, no path can end there at all, so its count is 0.

State Definitionf(r, c) is the number of obstacle-free paths from the start to cell (r, c), and it is 0 whenever (r, c) is blocked.

f(r, c) = 0 if the cell is an obstacle, otherwise f(r-1, c) + f(r, c-1)

Crucial Notea blocked cell is not a base case and it is not a place to stop the loop — it is an ordinary cell whose value happens to be zero. That distinction matters because zero propagates correctly all on its own. Cells downstream of an obstacle add in that zero, which contributes nothing, and their own counts come out right without any special handling. Trying to "skip" obstacles or break out of loops around them is how people write tangled, wrong code for this problem.

The base cases need care. Walking right along the top row, once you hit an obstacle every cell after it in that row is unreachable, because there is no row above to detour through. Same for the left column going down. If you blindly set the edges to all 1s, you will count paths that walk straight through a wall.

Building the table

The cleanest way to avoid edge-case bugs is to let the recurrence handle the edges too, by treating anything off the grid as zero:

python
def unique_paths_with_obstacles(grid):
    m, n = len(grid), len(grid[0])
    if grid[0][0] == 1 or grid[m - 1][n - 1] == 1:
        return 0                                  # blocked start or finish

    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1

    for r in range(m):
        for c in range(n):
            if grid[r][c] == 1:
                dp[r][c] = 0                      # unreachable; contributes nothing
                continue
            if r > 0: dp[r][c] += dp[r - 1][c]
            if c > 0: dp[r][c] += dp[r][c - 1]

    return dp[m - 1][n - 1]

The dp[0][0] = 1 before the loop is the empty path, and since (0,0) has no cell above or to its left, the loop leaves it alone. Every other edge cell now gets its value from its single in-grid neighbour, which is exactly right — including inheriting a zero if that neighbour was blocked.

The memoised top-down version says the same thing from the other end:

python
def unique_paths_with_obstacles(grid):
    m, n = len(grid), len(grid[0])
    memo = {}

    def f(r, c):
        if r < 0 or c < 0: return 0               # walked off the grid
        if grid[r][c] == 1: return 0              # blocked
        if r == 0 and c == 0: return 1            # reached the start
        if (r, c) in memo: return memo[(r, c)]
        memo[(r, c)] = f(r - 1, c) + f(r, c - 1)
        return memo[(r, c)]

    return f(m - 1, n - 1)

Note the order of the checks: the obstacle test comes before the start test, so a blocked starting cell correctly returns 0 rather than 1.

One row

The same overlapping-read trick works, with obstacles zeroing entries as we sweep:

python
def unique_paths_with_obstacles(grid):
    n = len(grid[0])
    row = [0] * n
    row[0] = 1
    for r in range(len(grid)):
        for c in range(n):
            if grid[r][c] == 1:
                row[c] = 0                        # this cell is unreachable
            elif c > 0:
                row[c] += row[c - 1]
    return row[n - 1]

When we reach column c, row[c] still holds the count from the row above and row[c-1] holds this row's already-updated value, so the single line adds exactly the two contributions we want. Setting row[c] = 0 on an obstacle wipes the inherited value from above, which is precisely the intended meaning: nothing can reach this cell, so nothing continues through it.

Worked Example:grid = [[0,0,0],[0,1,0],[0,0,0]]
The obstacle sits dead centre. Filling top-to-bottom, left-to-right:
- Row 0: 1 1 1 — the top row is clear, so one route to each.
- Row 1: (1,0) = above 1 + nothing to the left = 1. (1,1) is an obstacle → 0. (1,2) = above 1 + left 0 = 1. Row: 1 0 1.
- Row 2: (2,0) = above 1 = 1. (2,1) = above 0 + left 1 = 1. (2,2) = above 1 + left 1 = 2.

Answer 2 — go around the obstacle above it, or below it. Watch how the zero at the centre propagated: (2,1) correctly received nothing from above, but still picked up the route coming along the bottom.

Now a fully blocking case, [[0,1],[1,0]]: (0,1) is blocked → 0, (1,0) is blocked → 0, so (1,1) = 0 + 0 = 0. The robot is walled in, and the table reports it without any special check.

And the degenerate case [[1]]: the start is itself an obstacle, so the answer is 0.

What this teaches beyond the problem

Two ideas.

Constraints usually enter these tables as forbidden states, not as new logic. When a problem adds "you may not do X", the first thing to try is giving the offending states a neutral value — 0 for counting problems, infinity for minimisation problems, negative infinity for maximisation — and letting the existing recurrence carry it. Nine times out of ten the arithmetic does the work for you, and you avoid a thicket of special cases.

Watch what a new constraint does to your base cases. The recurrence here barely changed, but the edges did, and that is where the bugs live. In the empty grid, the whole top row was 1 by symmetry. With obstacles, that assumption silently walks through walls. Whenever you adapt a solved problem, re-derive the base cases from scratch rather than copying them across.

Exponential Plain Recursion
→
O(M × N) Time · O(M × N) Space Memoisation
→
O(M × N) Time · O(M × N) Space Tabulation
→
O(M × N) Time · O(N) Space One Row