Unique Paths II

Difficulty: Medium Source: NeetCode

Problem

A robot is at the top-left of an m x n grid. Some cells are obstacles (1), the rest are empty (0). The robot can only move right or down. Count how many unique paths reach the bottom-right corner. Return 0 if the start or end is blocked.

Example 1: Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] Output: 2

Example 2: Input: obstacleGrid = [[0,1],[0,0]] Output: 1

Constraints:

• 1 <= m, n <= 100
• obstacleGrid[i][j] is 0 or 1

Prerequisites

Before attempting this problem, you should be comfortable with:

• Unique Paths (62) — the base problem without obstacles
• 2D DP — filling a grid table based on neighbours

1. Brute Force / Recursive

Intuition

Same idea as Unique Paths, but we add one extra rule: if a cell contains an obstacle, it contributes 0 paths (we can’t pass through it). The robot still comes from the top or the left, and we recurse back from the destination.

Algorithm

1. If obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1, return 0.
2. Define dfs(i, j):
   • If out of bounds or obstacleGrid[i][j] == 1, return 0.
   • If i == 0 and j == 0, return 1.
   • Return dfs(i-1, j) + dfs(i, j-1).

Solution

def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    if obstacleGrid[0][0] == 1 or obstacleGrid[m - 1][n - 1] == 1:
        return 0

    def dfs(i, j):
        if i < 0 or j < 0 or obstacleGrid[i][j] == 1:
            return 0
        if i == 0 and j == 0:
            return 1
        return dfs(i - 1, j) + dfs(i, j - 1)

    return dfs(m - 1, n - 1)


print(uniquePathsWithObstacles([[0, 0, 0], [0, 1, 0], [0, 0, 0]]))  # 2
print(uniquePathsWithObstacles([[0, 1], [0, 0]]))                    # 1
print(uniquePathsWithObstacles([[1, 0]]))                             # 0

Complexity

• Time: O(2^(m+n)) — exponential without memoization
• Space: O(m+n) — recursion stack

2. Bottom-Up DP (Tabulation)

Intuition

Build the table left-to-right, top-to-bottom. Obstacle cells get 0. The first row and column are trickier than before — once you hit an obstacle on an edge, every cell after it on that edge is also 0 (the robot can’t get there at all). For interior cells, dp[i][j] = dp[i-1][j] + dp[i][j-1] as before, but obstacles short-circuit to 0.

Algorithm

1. Create a m x n dp table of zeros.
2. Fill dp[0][0] = 1 if not an obstacle.
3. Fill first column: dp[i][0] = dp[i-1][0] if obstacleGrid[i][0] == 0, else 0.
4. Fill first row: dp[0][j] = dp[0][j-1] if obstacleGrid[0][j] == 0, else 0.
5. For interior cells: if obstacle set 0, else dp[i-1][j] + dp[i][j-1].
6. Return dp[m-1][n-1].

Solution

def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    if obstacleGrid[0][0] == 1 or obstacleGrid[m - 1][n - 1] == 1:
        return 0

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

    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] if obstacleGrid[i][0] == 0 else 0

    for j in range(1, n):
        dp[0][j] = dp[0][j - 1] if obstacleGrid[0][j] == 0 else 0

    for i in range(1, m):
        for j in range(1, n):
            if obstacleGrid[i][j] == 1:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

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


print(uniquePathsWithObstacles([[0, 0, 0], [0, 1, 0], [0, 0, 0]]))  # 2
print(uniquePathsWithObstacles([[0, 1], [0, 0]]))                    # 1
print(uniquePathsWithObstacles([[1, 0]]))                             # 0

Complexity

• Time: O(m * n)
• Space: O(m * n) — reducible to O(n) with a rolling array

Common Pitfalls

Not checking the start/end for obstacles. If obstacleGrid[0][0] is blocked, the answer is immediately 0 — don’t let your code set dp[0][0] = 1 in that case.

Edge propagation along the border. Once an obstacle is hit on the first row or column, all subsequent cells in that row/column must be 0, not 1. A simple dp[i][0] = 1 loop will get this wrong.

Modifying the input grid. It’s tempting to write obstacleGrid[i][j] = paths directly, but this mutates the caller’s data. Use a separate dp table.