DSA AnimatorDSA animations
Unique Paths II LC #63 Medium 2D DP · Obstacles
Problem

Same as Unique Paths, but the grid has obstacles. obstacleGrid[r][c]=1 means blocked. Return the number of unique paths avoiding obstacles. Robot moves only right or down.

Example 1
Input: [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Example 2
Input: [[0,1],[0,0]]
Output: 1
Constraints: dp[r][c]=0 if blocked else top+left
Try Examples
Custom:
Approach
2D DP with Obstacles — dp[r][c]=0 if blocked else top+left
Same as Unique Paths but obstacle cells force dp=0. Paths cannot pass through blocked cells.
Grid with Obstacles
Load an example to begin.
Variables
cell (r,c)
—
top
—
left
—
paths
—
Step Logic
Press ▶ Play or Next Step to begin.
🎯
Ready
0 / 0
Select an example and press Play.
Algorithm
1
Obstacle cell: dp[c]=0 (no path through it)
2
Open cell: dp[r][c] = top + left (same as Unique Paths)
3
First row/col: propagate 0 after any obstacle
4
Answer = dp[m-1][n-1]
Time
O(m×n)
Space
O(n)
Why This Works

Obstacle cells cannot be reached, so dp=0. Open cells inherit top+left. A 0 propagates through adjacent cells that depend on it, correctly blocking all paths through the obstacle.

How to solve Unique Paths II

LeetCode 63 · Medium · Dynamic Programming · Pattern: 2D Grid DP

Why the obvious approach is slow

Exploring every path and checking for obstacles repeats the same work many times. The same recurrence as before still works.

The key idea

Use the same rule: paths into a cell equal paths from above plus paths from the left. But an obstacle cell gets 0, because no path can pass through it. This also handles obstacles in the first row or column: everything after them becomes 0. If the start itself is an obstacle, the answer is 0.

Remember

An obstacle simply forces the count to 0. In the rolling array, dp of c already holds the value from above.

Run the animation above on your own input, or watch the 1:52 video explanation of Unique Paths II with a dry run and Java code.

More Dynamic Programming problems