Unique Paths II

Problem

A robot starts in the top-left cell of a grid and may move only right or down. The grid now contains obstacles: obstacleGrid[i][j] == 1 marks a blocked cell the robot cannot enter, and 0 marks a free cell. Count the number of distinct right/down paths from the top-left to the bottom-right cell. If the start or the goal is blocked, the answer is 0.

Examples

• obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] → 2 — the single obstacle in the center leaves exactly two routes (hug the top-right corner or the bottom-left corner).
• obstacleGrid = [[0,1],[0,0]] → 1 — the only route is down then right.
• obstacleGrid = [[1,0]] → 0 — the start cell itself is blocked.

Constraints

• 1 <= m, n <= 100
• Each cell is 0 (free) or 1 (obstacle).
• The answer fits in a 32-bit signed integer.
• As in Unique Paths, the path count can be huge, so an O(m·n) DP is expected — enumeration is impossible.

Think about it first

TL;DR

The Unique Paths grid DP with one added rule — a blocked cell holds 0 paths — O(m·n) time, O(n) space with a rolling row.

Approach 1 — Brute force recursion

Branch right and down, but return 0 the moment we step onto an obstacle.

from typing import List

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])

        def paths(i: int, j: int) -> int:
            if i >= m or j >= n or obstacleGrid[i][j] == 1:
                return 0
            if i == m - 1 and j == n - 1:
                return 1
            return paths(i + 1, j) + paths(i, j + 1)

        return paths(0, 0)

Complexity: O(2^(m+n)) time — the same doubly-branching tree as Unique Paths, so the same cells are recomputed exponentially often. Infeasible at 100×100.

Approach 2 — Top-down memoization

The insight: the number of obstacle-free paths from (i, j) to the goal depends only on (i, j). Cache the cell and the exponential tree collapses to O(m·n) states — the obstacle check simply makes some states return 0.

State / recurrence. paths(i, j) = routes from (i, j) to the goal. Transition paths(i, j) = paths(i+1, j) + paths(i, j+1); return 0 if the cell is off-grid or blocked; return 1 at the goal (only reached when the goal is free).

from typing import List
from functools import lru_cache

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])

        @lru_cache(maxsize=None)
        def paths(i: int, j: int) -> int:
            if i >= m or j >= n or obstacleGrid[i][j] == 1:
                return 0
            if i == m - 1 and j == n - 1:
                return 1
            return paths(i + 1, j) + paths(i, j + 1)

        return paths(0, 0)

Complexity: O(m·n) time and space.

Approach 3 — Bottom-up tabulation (the 2-D table)

State / recurrence. dp[i][j] = number of paths from the start to cell (i, j). An obstacle blocks the cell entirely:

dp[i][j] = 0                          if obstacleGrid[i][j] == 1
dp[i][j] = dp[i-1][j] + dp[i][j-1]    otherwise (missing neighbors count as 0)

Seed dp[0][0] = 1 only when the start is free.

from typing import List

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                    continue
                if i > 0:
                    dp[i][j] += dp[i - 1][j]
                if j > 0:
                    dp[i][j] += dp[i][j - 1]
        return dp[m - 1][n - 1]

Walkthrough with obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]. Top row fills to [1,1,1] and the first column to 1,1,1. The center dp[1][1] is an obstacle → 0. Then dp[1][2] = dp[0][2] + dp[1][1] = 1 + 0 = 1, dp[2][1] = dp[1][1] + dp[2][0] = 0 + 1 = 1, and finally dp[2][2] = dp[1][2] + dp[2][1] = 1 + 1 = 2.

Complexity: O(m·n) time, O(m·n) space.

Approach 4 — Space-optimized rolling row

The insight: row i only reads row i-1, so one array suffices. When a cell is blocked, set its slot to 0; otherwise add the slot to its left (row[j-1], already updated for this row) into row[j] (still holding the row-above value).

from typing import List

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        row = [0] * n
        row[0] = 1 if obstacleGrid[0][0] == 0 else 0
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    row[j] = 0
                elif j > 0:
                    row[j] += row[j - 1]
        return row[n - 1]

Complexity: O(m·n) time, O(n) space.

Common pitfalls

• Initializing the whole first row/column to 1 as in Unique Paths — wrong here, because an obstacle in row 0 zeroes out every cell to its right. Build the base cells through the recurrence instead.
• Forgetting the start cell may itself be an obstacle, which must yield 0.
• In the rolling-row version, resetting row[0] inside the loop: leave it to the obstacle check (row[0] becomes 0 the first time its column hits an obstacle and stays there).
• Adding a neighbor without a bounds guard (i > 0, j > 0), which would wrap around to the last index in Python.

Pattern takeaway

Obstacles are a masking layer on top of an existing grid DP: keep the same “sum of top and left” recurrence and force blocked cells to the identity-for-counting value, 0. The general move — start from the clean recurrence, then overlay constraints as forced values — recurs throughout grid DP (blocked cells, forbidden transitions, minimum-cost floors).