Unique Paths II Solution

Problem

A robot starts at the top-left cell of an m×n grid and wants to reach the bottom-right cell, moving only right or down. Some cells contain obstacles. Count the number of distinct paths from start to finish that avoid every obstacle.

0 0 0
0 1 0
0 0 0

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: The center cell is blocked; only the top-edge route and the left-edge route survive.

Counter-example: if the start or finish cell itself contains an obstacle, the answer is 0 — no path can begin or end there.

Intuition

The number of ways to reach any cell equals the ways to reach the cell directly above plus the ways to reach the cell directly to the left, because those are the only two directions the robot can come from. An obstacle forces that cell's count to zero, which automatically prevents any downstream cell from counting a path through it. Fill the table one cell at a time from top-left to bottom-right and the answer accumulates naturally.

Approach 1 — 2D DP

Allocate an m×n table. Each entry stores the path count to that cell. Obstacles write a zero and silently block further propagation through them.

Set dp[0][0] = 1 if the start is clear, else 0.
Fill the first column top-to-bottom: each cell inherits the cell above's count, or 0 if it holds an obstacle.
Fill the first row left-to-right: each cell inherits the cell to its left's count, or 0 if it holds an obstacle.
For every remaining cell: if an obstacle, write 0; otherwise write dp[row-1][col] + dp[row][col-1].
Return dp[rows-1][cols-1].

1def uniquePathsWithObstacles(obstacleGrid: list[list[int]]) -> int:
2    rows, cols = len(obstacleGrid), len(obstacleGrid[0])
3    dp = [[0] * cols for _ in range(rows)]
4    dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0
5    for row in range(1, rows):
6        dp[row][0] = dp[row - 1][0] if obstacleGrid[row][0] == 0 else 0
7    for col in range(1, cols):
8        dp[0][col] = dp[0][col - 1] if obstacleGrid[0][col] == 0 else 0
9    for row in range(1, rows):
10        for col in range(1, cols):
11            if obstacleGrid[row][col] == 1:
12                dp[row][col] = 0
13            else:
14                dp[row][col] = dp[row - 1][col] + dp[row][col - 1]
15    return dp[rows - 1][cols - 1]

Time: O(m × n) — every cell is visited exactly once. Space: O(m × n) — the full grid-sized DP table.

Approach 2 — Space-Optimized 1D DP

Keep only a single row array. Before the inner loop updates dp[col], its old value represents paths from above (the previous row); dp[col-1], already updated this iteration, represents paths from the left.

Initialize dp[0] = 1 if the start is clear, else 0.
Fill the first row: propagate dp[col-1] rightward, zeroing at any obstacle.
For each subsequent row: reset dp[0] to 0 if the first-column cell has an obstacle (it has no left neighbor, only from-above).
For each remaining column: dp[col] = 0 if obstacle, else dp[col] + dp[col-1].
Return dp[cols-1].

1def uniquePathsWithObstacles(obstacleGrid: list[list[int]]) -> int:
2    cols = len(obstacleGrid[0])
3    dp = [0] * cols
4    dp[0] = 1 if obstacleGrid[0][0] == 0 else 0
5    for col in range(1, cols):
6        dp[col] = dp[col - 1] if obstacleGrid[0][col] == 0 else 0
7    for row in range(1, len(obstacleGrid)):
8        dp[0] = dp[0] if obstacleGrid[row][0] == 0 else 0  # only from above
9        for col in range(1, cols):
10            if obstacleGrid[row][col] == 1:
11                dp[col] = 0
12            else:
13                dp[col] = dp[col] + dp[col - 1]  # old dp[col]=from above, dp[col-1]=from left
14    return dp[-1]

Time: O(m × n) — same traversal as Approach 1. Space: O(n) — only one row of length cols kept in memory at any time.

Complexity Summary

Approach	Time	Space	When to use
2D DP	O(m × n)	O(m × n)	When clarity and debuggability matter more than memory
Space-Optimized 1D DP	O(m × n)	O(n)	When the grid is large and O(m × n) extra memory is a constraint

Common Mistakes

Hard-coding dp[0][0] = 1 without checking for an obstacle — if the start cell itself is blocked, the answer is 0; unconditionally setting it to 1 silently corrupts every result.
Not zeroing out cells beyond an obstacle in the first row or column — once any cell in the first row or column is blocked, every cell to its right (or below it) is also unreachable through that edge; the propagation must stop at the first obstacle, not continue with the last valid count.
Forgetting to update dp[0] separately in the 1D approach — the leftmost cell of each row has no left neighbor, so it can only receive paths from directly above; it must be zeroed when its column-0 cell is an obstacle, not added to dp[col-1].
Applying the recurrence to obstacle cells — an obstacle cell must be explicitly zeroed regardless of what its neighbors hold; skipping the obstacle check lets phantom paths route through blocked squares.
Missing the cast in C++ — vector::size() returns size_t (unsigned); using it directly in a signed comparison or subtracting from it on an empty grid causes silent wrap-around; cast to int before using in loops.

Unique Paths II — Solution