This is a direct extension of the classic "Unique Paths" problem, with one twist: some cells are blocked by obstacles. The robot still starts at the top-left and needs to reach the bottom-right, moving only right or down. But now, any cell containing a 1 is impassable, and no valid path can go through it.

The key question becomes: how do obstacles affect the number of reachable paths? In the original problem, every cell was reachable and contributed paths from its top and left neighbors. Here, an obstacle cell contributes zero paths. It's a dead end. Any path that would have gone through that cell simply doesn't exist.

There's also a subtle edge case to watch for: if the start cell (0, 0) or the destination cell (m-1, n-1) is itself an obstacle, the answer is immediately 0. No path can begin at a wall, and no path can end at one either.

Key Constraints:

Intuition

The most natural starting point is recursion. From any cell (i, j), the robot has two choices: go right to (i, j + 1) or go down to (i + 1, j). The total number of paths from (i, j) to the destination is the sum of paths from those two neighbors. If a cell is an obstacle, it returns 0 because no path can pass through it.

This approach correctly handles obstacles by simply treating them as dead ends in the recursion tree. But it has the same fundamental flaw as the brute force for Unique Paths: it recomputes the same subproblems an exponential number of times.

Algorithm

Example Walkthrough

Input:

The recursion explores all possible paths. From (0,0), it tries going right and going down. Whenever it hits the obstacle at (1,1), that branch returns 0. The two surviving paths are: Right -> Right -> Down -> Down, and Down -> Down -> Right -> Right. Result: 2.

Code

The recursion recomputes the same cells over and over. There are only m * n distinct subproblems, but we solve each one many times. What if we built the answer bottom-up, computing each cell exactly once?

Intuition

Instead of recursing from the top-left and caching results, we can build the answer bottom-up with a 2D DP table. Define dp[i][j] as the number of unique paths from (0, 0) to cell (i, j). The recurrence is the same as the original Unique Paths problem:

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

But with one critical modification: if obstacleGrid[i][j] == 1, then dp[i][j] = 0. No path can end at an obstacle, period.

The first row and first column need special attention. In the obstacle-free version, they're all 1s. But here, an obstacle in the first row blocks everything to its right (since the only way to reach those cells is by moving right from the start). Similarly, an obstacle in the first column blocks everything below it.

Algorithm

Example Walkthrough

Code

The time complexity is already optimal, but we're using O(m * n) space for the DP table. When filling row i, we only ever look at row i - 1. What if we used a single 1D array and updated it in-place as we process each row?

Intuition

The 2D DP table has an interesting property: to compute dp[i][j], we only need dp[i-1][j] (directly above) and dp[i][j-1] (directly to the left). We never look back more than one row. So instead of a full 2D table, we can use a single 1D array of size n.

Here's the trick. We process the grid row by row. At the start of processing row i, our 1D array dp[j] holds the values from row i - 1. As we sweep left to right across the row, we update each dp[j] to become the value for row i:

So dp[j] = dp[j] + dp[j-1] naturally combines the top and left contributions. When we hit an obstacle, we set dp[j] = 0.

Algorithm

Example Walkthrough

Code