Problem statement

A robot starts at the top-left corner of an m × n grid and wants to reach the bottom-right corner, moving only down or right.

Some cells contain obstacles, marked 1; empty cells are 0. Return the number of distinct paths that avoid every obstacle. If the start or the finish is blocked, the answer is 0.

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

Example 3

Input: obstacleGrid = [[1]]
Output: 0
Explanation: The starting cell itself is blocked.

Constraints

• 1 <= obstacleGrid.length, obstacleGrid[i].length <= 8
• obstacleGrid[i][j] is 0 or 1.
• The answer fits in a signed 32-bit integer.

Hints for Unique Paths II

1. Hint 1

   Without obstacles, the count of paths to a cell is the sum of the counts above it and to its left.

2. Hint 2

   An obstacle sets that cell's count to 0 — nothing can pass through it.

3. Hint 3

   Seed the start with 1, and remember the start itself may be blocked.

How to solve Unique Paths II

Paths to a cell are the sum of paths to the cell above and the cell to the left, except an obstacle cell has zero paths.

Approach

1. Return 0 if the start is blocked; otherwise dp[0][0] = 1.
2. In row-major order, set dp[r][c] = 0 for an obstacle, else add dp[r-1][c] and dp[r][c-1] where they exist.
3. Return dp[m-1][n-1].

Why it works

Each path ends with a down or right move, so path counts decompose over the last step; zeroing obstacles removes every path through them from all later sums.

Complexity

• Time — O(m · n)
• Space — O(m · n), reducible to one row

Pitfalls

• The first row and column are not all ones once an obstacle appears in them — everything after the obstacle is 0.
• A blocked finish yields 0 automatically.

Reference solution

Python

def uniquePathsWithObstacles(obstacleGrid) -> int:
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    if obstacleGrid[0][0] == 1:
        return 0
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1
    for r in range(m):
        for c in range(n):
            if obstacleGrid[r][c] == 1:
                dp[r][c] = 0
                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]

Java

public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
    if (obstacleGrid[0][0] == 1) return 0;
    int[][] dp = new int[m][n];
    dp[0][0] = 1;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (obstacleGrid[r][c] == 1) { dp[r][c] = 0; 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];
}

C++

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m = (int) obstacleGrid.size(), n = (int) obstacleGrid[0].size();
    if (obstacleGrid[0][0] == 1) return 0;
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = 1;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (obstacleGrid[r][c] == 1) { dp[r][c] = 0; 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];
}

JavaScript

var uniquePathsWithObstacles = function(obstacleGrid) {
    const m = obstacleGrid.length, n = obstacleGrid[0].length;
    if (obstacleGrid[0][0] === 1) return 0;
    const dp = [];
    for (let r = 0; r < m; r++) dp.push(new Array(n).fill(0));
    dp[0][0] = 1;
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (obstacleGrid[r][c] === 1) { dp[r][c] = 0; 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];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium