#63 Unique Paths II
frequently reported atBloombergAmazonGoogleMicrosoftGoldman Sachs
the problem
In plain words
Same robot, same moves (only right or down), but now the m × n grid has rocks: obstacleGrid[r][c] = 1 is a rock and 0 is free. The robot can't step on a rock. Count the paths from the top-left to the bottom-right.
in obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
out 2
The rock in the middle leaves right-right-down-down and down-down-right-right.
in obstacleGrid = [[0,1],[0,0]]
out 1
- 1 ≤ m, n ≤ 100
- obstacleGrid[r][c] is 0 or 1
- The answer is ≤ 2·10⁹
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGrid DP
Exactly Unique Paths with one extra rule: a rock cell has 0 paths into it. That 0 then flows into its neighbours on its own — and if the start itself is a rock, everything is 0.
solutions
From brute force to optimal
paths(r, c) = 0 on a rock or off the grid, 1 at the start, else paths(r − 1, c) + paths(r, c − 1).
- Check rock / off-grid first.
- Start cell → 1.
- Sum the two sub-calls.
Two branches per step over a path of length m + n − 2.
Recursion depth.
class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { return paths(obstacleGrid, obstacleGrid.length - 1, obstacleGrid[0].length - 1); } /** Paths from (0,0) to (r,c) moving only right/down, never stepping on a 1. */ private int paths(int[][] grid, int r, int c) { if (r < 0 || c < 0 || grid[r][c] == 1) return 0; // off the grid or a rock: no way in if (r == 0 && c == 0) return 1; // standing on the start return paths(grid, r - 1, c) + paths(grid, r, c - 1); }}Cache paths(r, c); −1 = unknown because 0 paths is a real answer here.
- int[][] memo filled with −1.
- Check, compute, store.
Each cell once.
Memo + stack.
class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length, n = obstacleGrid[0].length; int[][] memo = new int[m][n]; for (int[] row : memo) Arrays.fill(row, -1); // -1 = not computed (0 paths is a real answer) return paths(obstacleGrid, m - 1, n - 1, memo); } private int paths(int[][] grid, int r, int c, int[][] memo) { if (r < 0 || c < 0 || grid[r][c] == 1) return 0; if (r == 0 && c == 0) return 1; if (memo[r][c] != -1) return memo[r][c]; return memo[r][c] = paths(grid, r - 1, c, memo) + paths(grid, r, c - 1, memo); }}Fill row by row: rock → 0, start → 1, else above + left.
- dp[r][c] = 0 on a rock.
- dp[0][0] = 1 if free.
- Otherwise add the cell above and the cell to the left (when they exist).
One O(1) step per cell.
The table.
class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length, n = obstacleGrid[0].length; int[][] dp = new int[m][n]; // dp[r][c] = paths that reach (r, c) for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { if (obstacleGrid[r][c] == 1) dp[r][c] = 0; // a rock: nobody gets in else if (r == 0 && c == 0) dp[r][c] = 1; // the start else dp[r][c] = (r > 0 ? dp[r - 1][c] : 0) + (c > 0 ? dp[r][c - 1] : 0); } } return dp[m - 1][n - 1]; }}Same one-row trick as Unique Paths, with rocks forcing dp[c] = 0.
- dp[0] = 1.
- For each row, for c = 0..n − 1: rock → dp[c] = 0; else if c > 0, dp[c] += dp[c − 1].
- Return dp[n − 1].
Same updates.
One row.
class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int n = obstacleGrid[0].length; int[] dp = new int[n]; // dp[c] = paths into column c of the current row dp[0] = 1; // one way to stand on the start (zeroed below if it's a rock) for (int[] row : obstacleGrid) { for (int c = 0; c < n; c++) { if (row[c] == 1) dp[c] = 0; // a rock blocks every path through it else if (c > 0) dp[c] += dp[c - 1]; // old dp[c] = from above, dp[c-1] = from the left } } return dp[n - 1]; }}in the room
How to say it in the interview
talk track
- "Same recurrence as Unique Paths; a rock forces 0."
- Name the traps before coding: rock on the start or the goal → 0, and after a rock the top row is no longer all 1s.
- Then the one-row version: dp[c] = rock ? 0 : dp[c] + dp[c − 1].
traps
- Filling the whole top row and left column with 1s: after a rock, the rest of that edge is unreachable.
- Forgetting a rock on the start cell → the answer must be 0.
- The combinatorics formula from Unique Paths no longer works with rocks.
what they ask next
Follow-ups
What if the robot may also move up or left?
Then paths can loop forever. Counting simple paths needs backtracking; the shortest path needs BFS — like finding a route on a game map.
before you submit
Edge cases to test
- Rock on the start or on the goal → 0.
- A rock in the top row: every cell to its right in that row has 0 paths.
- 1 × 1 free → 1; 1 × 1 rock → 0.
practise next
Similar problems
- #62Unique PathsMediumin Dynamic Programming
- #64Minimum Path SumMediumin Dynamic Programming
- #1091Shortest Path in Binary MatrixMediumin Graphs