Unique Paths with Obstacles
Maintained by Vikas D, software engineer
You are handed a grid of `0`s and `1`s. A `0` marks an open cell you can stand on, and a `1` marks a blocked cell you must avoid. A traveler begins at the top-left cell and wants to reach the bottom-right cell.
On each move the traveler may step one cell to the right or one cell down, nothing else. There is no moving up, left, or diagonally, so every route is a monotone walk toward the lower-right.
Your job is to return the number of complete routes that reach the destination without ever landing on a blocked cell. If the start or the destination itself is blocked, no valid route exists and the answer is zero.
The grid always has at least one cell. The single-cell grid counts as one route when it is open and zero routes when it is blocked.
Examples
The only block sits in the middle. A route can hug the top edge then the right edge, or hug the left edge then the bottom edge. Both skirt the obstacle, giving two routes.
The top-right cell is blocked, so going right first is a dead end. The traveler must go down, then right, which is the single surviving route.
The starting cell is itself blocked, so the traveler cannot even begin. There are no valid routes.
Constraints
- m == obstacleGrid.length, n == obstacleGrid[0].length
- 1 <= m, n <= 100
- Each cell is either 0 (open) or 1 (blocked)
- Moves are limited to one step right or one step down
Visible test cases
- uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]]) == 2
- uniquePathsWithObstacles([[0,1],[0,0]]) == 1
- uniquePathsWithObstacles([[1]]) == 0
- uniquePathsWithObstacles([[0]]) == 1
- uniquePathsWithObstacles([[0,0],[1,0]]) == 1
Hints
Hint 1
The number of ways to reach a cell only depends on the two neighbours directly above it and directly to its left, since those are the only cells that can lead into it.
Hint 2
A blocked cell contributes zero ways to anything downstream, so set its count to 0 instead of summing its neighbours.
Hint 3
You never look at the row above the previous one, so a single rolling array of width n is enough to carry the counts forward row by row.
Approaches
Recursive enumeration
Time O(2^(m+n)) without memoization because each cell forks into two recursive calls · Space O(m+n) for the recursion depthDefine a function that returns the route count from a given cell to the destination, branching into the right move and the down move, and let recursion explore every walk.
- If a cell is off the grid or blocked, return 0 ways.
- If a cell is the destination, return 1 way.
- Otherwise return the sum of the ways from the cell to the right and the cell below.
- Call the function from the start cell and return its result.
Bottom-up DP with a rolling row
Time O(m*n) since each cell is visited once · Space O(n) for the single rolling arrayFill route counts in reading order so that by the time you reach a cell, its top and left neighbours are already known, and reuse one array across rows to keep memory flat.
- If the start cell is blocked, return 0 immediately.
- Create a counts array of width n, all zero, then set the first entry to 1 to seed the start.
- Walk the grid row by row, left to right. For a blocked cell set its count to 0.
- For an open cell beyond the first column, add the left neighbour's current count to it; the value already sitting there is the count carried down from the row above.
- After the final row, the last entry of the array holds the route count to the destination.
Common mistakes
- Forgetting that the start or destination cell can itself be blocked, which must short-circuit to 0.
- Seeding the first row or column as all 1s the way the obstacle-free version does; here a block partway along an edge must cut off every cell after it on that edge.
- Adding the left neighbour for a blocked cell instead of zeroing it, which lets paths leak through obstacles.
- Using a number type that overflows on large grids; in JavaScript the counts can exceed the safe integer range for a 100 by 100 open grid, though the given constraints keep test cases small.
Follow-up variations
- Return one actual valid route, not just the count, by tracing back through the counts.
- Allow diagonal moves as well and adjust the recurrence to pull from three neighbours.
- Find the route count with the minimum total weight when each cell carries a cost.
- Handle a streaming grid where rows arrive one at a time and you must update counts on the fly.