63. Unique Paths II

MediumTwo-Dimensional Dynamic Programming2D dynamic programmingGrid path-counting DP with obstacles

Unique Paths II

A robot starts at the top-left of an m x n grid and moves only right or down to reach the bottom-right. Some cells contain obstacles marked 1 (empty cells are 0), which the robot cannot enter. Return the number of distinct obstacle-free paths.

Open official problem prompt ↗

In plain English

We want to count right/down paths across the grid while never stepping on a blocked cell.

Picture it like this

Water flowing downhill and rightward through a grid of pipes where obstacle cells are plugged, so flow reroutes around them.

Example

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Why: The single obstacle in the center leaves exactly two ways around it: right-right-down-down and down-down-right-right.

Constraints

m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j] is 0 or 1.

Pattern lesson

See the pattern, then code

Grid path-counting DP with obstacles

↗

Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. An obstacle cell contributes no paths, so set its count to 0; every other cell still sums its top and left neighbors, which naturally routes counts around blocks.

New words, made simpleKnow these before the algorithm

Obstacle: A cell marked 1 that the robot cannot occupy.
Blocked start/end: If the start or destination is an obstacle, zero paths exist.
Additive recurrence: A free cell's count is the sum of reachable top and left neighbors.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Enumerate all paths

Exponential and wasteful given overlapping subproblems.

Recurse over right/down moves, abandoning any path that hits an obstacle.

Time O(2^(m+n))Space O(m+n)

Best choice2D grid DP with zeroing

Linear in grid size and handles blocks cleanly; the recommended solution.

Same additive fill as Unique Paths, but obstacle cells are set to 0.

Time O(m*n)Space O(m*n)

The rule we keep true

Invariant

dp[i][j] equals the number of obstacle-free right/down paths from the start to cell (i,j), and is 0 for any blocked or unreachable cell.

Why this is correct

Reasoning

A blocked cell truly has zero routes, so forcing dp=0 there prevents any path from passing through it. Free cells still receive exactly the paths arriving from above or the left, which are disjoint and complete, so the counts remain correct around obstacles by induction.

The algorithm in three movesSay these aloud before coding

1If a cell is an obstacle, set dp = 0

dp row0 = 1 1 1

2Set the start cell to 1 only if it is not an obstacle

dp row1 = 1 0 1

3Otherwise dp[i][j] = (top neighbor if it exists) + (left neighbor if it exists)

dp row2 = 1 1 2

4Return dp[m-1][n-1]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readgrid[0][0]=0

2 · AskIs the start blocked?

3 · Update statedp[0][0] = 1

4 · Resultone path at origin

Key takeaway

The 3x3 grid with the blocked center cell (X); counts flow around it.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6-7Zero out obstacles
A blocked cell can never be reached, so its count is 0 and paths route around it.
2
Lines 8-9Start cell
The origin has one path only if it is not itself an obstacle.
3
Lines 10-13Guarded recurrence
Add the top neighbor only when i>0 and the left only when j>0 to stay in bounds.
4
Lines 14Return
The destination cell holds the obstacle-free path count (0 if it is blocked).

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Start cell is an obstacle returns 0
Destination cell is an obstacle returns 0
An obstacle fully walling off a row or column can make the answer 0

Common beginner mistakes

Initializing the whole grid to 1 like Unique Paths I, which ignores blocked edges
Continuing to propagate counts through an obstacle instead of zeroing it
Forgetting that a blocked start immediately yields 0

Check your understanding

Why can't we just seed the first row and column to all 1s as in Unique Paths I?

PyPython 3 · solution.py

Optimal

1class Solution:2    def uniquePathsWithObstacles(self, obstacleGrid: list[list[int]]) -> int:3        m, n = len(obstacleGrid), len(obstacleGrid[0])4        dp = [[0] * n for _ in range(m)]5        for i in range(m):6            for j in range(n):7                if obstacleGrid[i][j] == 1:8                    dp[i][j] = 09                elif i == 0 and j == 0:10                    dp[i][j] = 111                else:12                    top = dp[i - 1][j] if i > 0 else 013                    left = dp[i][j - 1] if j > 0 else 014                    dp[i][j] = top + left15        return dp[m - 1][n - 1]

Time complexityO(m*n)Optimized

Space complexityO(m*n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftBloomberg

Unique Paths II

Unique Paths II

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Two-Dimensional Dynamic Programming