DSA problem
Unique Paths II
You are given an m x n integer matrix obstacleGrid where 0 represents an empty cell and 1 represents an obstacle. A robot starts at (0, 0) and wants to reach (m - 1, n - 1), moving only right or down at each step and never stepping on an obstacle. Return the number of unique paths.
The structure is identical to "Unique Paths," but with an extra rule: any cell marked 1 contributes 0 paths. The recurrence dp[i][j] = dp[i - 1][j] + dp[i][j - 1] still holds for every empty cell. The only edits are that whenever the current cell is an obstacle we force dp[i][j] = 0, and the first-row / first-column base cases must respect obstacles too: once an obstacle appears in row 0, every cell to its right in row 0 becomes unreachable, and similarly down column 0.
A common mistake is to initialize row 0 and column 0 to all 1s without checking for obstacles — that double counts paths that should not exist. The cleanest fix is to set dp[0][0] = 1 - obstacleGrid[0][0] (so a blocked start gives 0 immediately) and then derive the rest of row 0 and column 0 from the recurrence using their single neighbor.
The optimal space-optimized version reuses a single dp array of length n exactly like the no-obstacle variant. We walk each row left-to-right; if obstacleGrid[i][j] == 1 we zero out dp[j], otherwise we add dp[j - 1] (the from-the-left count) into dp[j] (the from-above count, still sitting from the previous row). This runs in O(m * n) time and O(n) space.
Examples
obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]2obstacleGrid = [[0,1],[0,0]]1obstacleGrid = [[1]]0Constraints
- 1 <= m, n <= 100
- Every cell of `obstacleGrid` is either 0 (empty) or 1 (obstacle).
- The robot may move only right or down at each step.
- A cell with value 1 may not be visited.
- The answer is guaranteed to fit in a 32-bit signed integer.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.