Unique Paths II
Problem
m × n grid and wants
to reach the bottom-right cell, moving only right or down. Cells marked
1 are obstacles that cannot be entered. Count the distinct paths
(0 if the start or end is blocked).[[0,0,0],[0,1,0],[0,0,0]]Output2[[0,1],[0,0]]Output1[[1]]Output01 ≤ m, n ≤ 100 · grid[i][j] ∈ {0, 1} · answer ≤ 2·109
Try it yourself
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
}
}
Instinct Grid moves that never loop back (right/down, row to row) plus "count or optimise the paths" - build dp[r][c] from the cells that can step in.
Memory hack Every cell asks its parents - a cell's answer comes only from the neighbours that can move into it, so fill cells in the order they arrive.
Open the Grid DP guide →Approaches
Brute ForceRecursion (Try Right & Down)
O(2m+n)Space O(m + n)From (row, col) the number of paths to the goal is the sum
of paths after stepping right and after stepping down. Leaving the grid or
hitting an obstacle contributes 0; reaching the goal contributes 1.
public int uniquePathsWithObstacles(int[][] obstacleGrid) { return countPaths(0, 0, obstacleGrid); } private int countPaths(int row, int col, int[][] grid) { if (row >= grid.length || col >= grid[0].length || grid[row][col] == 1) return 0; // off-grid or blocked if (row == grid.length - 1 && col == grid[0].length - 1) return 1; return countPaths(row, col + 1, grid) + countPaths(row + 1, col, grid); }
Direct translation of the rules, but the same cells are re-solved exponentially often.
BetterTop-Down Memoization
O(m · n)Space O(m · n)The answer for a cell never changes, so cache it in
memo[row][col] (-1 = not computed). Each of the
m·n cells is solved once; the recursion stack adds O(m + n).
public int uniquePathsWithObstacles(int[][] obstacleGrid) { int[][] memo = new int[obstacleGrid.length][obstacleGrid[0].length]; for (int[] row : memo) Arrays.fill(row, -1); return countPaths(0, 0, obstacleGrid, memo); } private int countPaths(int row, int col, int[][] grid, int[][] memo) { if (row >= grid.length || col >= grid[0].length || grid[row][col] == 1) return 0; if (row == grid.length - 1 && col == grid[0].length - 1) return 1; if (memo[row][col] != -1) return memo[row][col]; return memo[row][col] = countPaths(row, col + 1, grid, memo) + countPaths(row + 1, col, grid, memo); }
Linear in the grid size, but uses a full memo table plus recursion.
OptimalBottom-Up 1D DP (Rolling Row)
O(m · n)Space O(n)Keep dp[j] = paths into column j of the current
row. Before updating, dp[j] still holds the value from the row
above and dp[j-1] is already the current row’s
left cell, so dp[j] += dp[j-1]; an obstacle resets it to 0.
public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length, n = obstacleGrid[0].length; int[] dp = new int[n]; dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (obstacleGrid[i][j] == 1) dp[j] = 0; // blocked else if (j > 0) dp[j] += dp[j - 1]; // above + left } } return dp[n - 1]; }
Dry run[[0,0,0],[0,1,0],[0,0,0]] (dp after each row)
- row 0111only from the left
- row 110X1obstacle → dp[1]=0
- row 2112dp[2]=1+1 → 2 ✔
Iterative, no recursion, O(n) memory — the interview answer.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Recursion (Try Right & Down) | O(2m+n) | O(m + n) |
| Better | Top-Down Memoization | O(m · n) | O(m · n) |
| Optimal | Bottom-Up 1D DP (Rolling Row) | O(m · n) | O(n) |
- Initialising the first row/column to all 1s — cells past an obstacle are unreachable.
- Ignoring a blocked start or end cell — the answer must be 0.
- Forgetting to zero
dp[j]on an obstacle — stale value from the row above leaks.
- Start from Unique Paths (62) and add one rule: obstacle → 0.
- Show recursion → memo → table → 1D as a natural progression.
- Point out the recursion depth is only m + n, but the tree is exponential.