Unique Paths II
Problem Statement
A robot starts in the top-left corner of an m x n grid and wants to reach the bottom-right corner. The robot may move only down or right. Some cells contain obstacles and cannot be used. Return the number of distinct valid paths.
Input
A 2D integer grid obstacleGrid, where 1 marks a blocked cell and 0 marks an open cell.
Output
An integer: the number of valid paths from the top-left cell to the bottom-right cell without stepping on obstacles.
Constraints
- •
m == obstacleGrid.length - •
n == obstacleGrid[i].length - •
1 <= m, n <= 100 - •
obstacleGrid[i][j] is **0** or **1** - •
**0** means empty and **1** means blocked
Examples
Example 1
obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
2Example 2
obstacleGrid = [[0,1],[0,0]]
1Example 3
obstacleGrid = [[1]]
0Learning Objectives
- Extend grid path counting by treating blocked cells as zero-way states.
- Handle blocked start and finish cells naturally through the recurrence.
- Update a 1D row array without letting paths flow through obstacles.
- Explain why an obstacle resets the current cell rather than subtracting paths later.
Intuition
This is the same top-and-left path-counting problem, except blocked cells cannot receive or send paths. A blocked cell has exactly 0 ways to stand on it, regardless of how many paths could reach its top or left neighbours.
That local reset is the simplest way to think about obstacles. When processing a free cell, add top and left as usual. When processing an obstacle, overwrite the cell count with 0 so future cells do not accidentally inherit paths through it.
The 1D version uses the same meaning as Unique Paths. Before the update, ways[j] is the number of paths from the cell above. After the update, it becomes the number of paths to the current cell. If the current cell is blocked, setting ways[j] = 0 cuts off both this cell and any cells that would use it as their left neighbour.
Common mistakes
- ×Only checking obstacles after computing the answer, which allows paths to pass through blocked cells.
- ×Forgetting that a blocked start cell should produce zero paths.
- ×Leaving **ways[col]** unchanged at an obstacle, which leaks paths from the row above.
- ×Initialising the whole first row to one without stopping after the first obstacle.
- ×Using right-to-left 1D updates, which breaks the left-neighbour dependency.
State Definition
Let dp[i][j] be the number of valid paths from (0, 0) to cell (i, j) without stepping on any obstacle. If obstacleGrid[i][j] = 1, then dp[i][j] = 0. The answer is dp[m - 1][n - 1].
For the space-optimized version, ways[j] stores the current row value for column j after obstacles have been applied.
State Transition
If the current cell is blocked, the transition is forced:
dp[i][j] = 0
Otherwise, paths come from top and left:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
Out-of-bounds neighbours contribute 0, while the start cell contributes 1 only if it is open. In the 1D version, each free non-first-column cell performs ways[j] = ways[j] + ways[j - 1]; each obstacle performs ways[j] = 0.
Solutions
Solution: Space-optimized row DP with obstacle resets
Use one row of path counts and scan every cell from left to right. Free cells add the top count and left count; obstacle cells reset the current column to zero immediately.
Step-by-step
- Create ways with one entry per column and set ways[0] = 1 as the potential starting path.
- Visit every cell row by row.
- If a cell is blocked, set ways[col] = 0.
- Otherwise, if col > 0, add ways[col - 1] into ways[col].
- Return ways[cols - 1] after the last row is processed.
O(m · n)
O(n)
Each grid cell is processed once, and the DP state stores one row.
Java implementation
Dry Run
Sample input
obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]. The middle cell blocks all paths through row 1, column 1.
| cell | blocked | top value | left value | ways after update |
|---|---|---|---|---|
| (0,0) | no | 1 | none | [1,0,0] |
| (0,1) | no | 0 | 1 | [1,1,0] |
| (0,2) | no | 0 | 1 | [1,1,1] |
| (1,0) | no | 1 | none | [1,1,1] |
| (1,1) | yes | 1 | 1 | [1,0,1] |
| (1,2) | no | 1 | 0 | [1,0,1] |
| (2,0) | no | 1 | none | [1,0,1] |
| (2,1) | no | 0 | 1 | [1,1,1] |
| (2,2) | no | 1 | 1 | [1,1,2] |
The obstacle at (1, 1) resets the middle column to zero for that row. By the bottom-right cell, the two surviving routes contribute 2 paths.
Complexity Analysis
Obstacle handling does not change the asymptotic cost. The only new operation is a constant-time reset to zero when a blocked cell is encountered.
Space-optimized row DP with obstacle resets
O(m · n)
O(n)
Each grid cell is processed once, and the DP state stores one row.
Interview Tips
Present this as Unique Paths with a blocking rule. The most important implementation detail is that an obstacle must overwrite the current DP value with zero immediately. That one line correctly handles obstacles in the first row, first column, start cell, and finish cell without special-case branches.
Likely follow-ups
- What if obstacles can appear after each move and the grid changes over time?
- How would you return one actual valid path instead of the count?
- How does the solution change if the robot can move up or left as well?
- Can you count paths modulo a large prime when the answer may be huge?
Similar Problems
Key Takeaways
- A blocked cell is a DP state with zero valid paths.
- Reset obstacle cells immediately so later cells cannot inherit invalid paths.
- The 1D row update still works because top and left remain the only dependencies.
- A careful recurrence can eliminate most obstacle edge cases.