Unique Paths II: DP with Obstacles

You have a robot sitting in the top-left corner of an m x n grid. It can only move right or down. Some cells contain obstacles. How many unique paths exist from the top-left to the bottom-right corner?

This is LeetCode 63: Unique Paths II, and it is the natural follow-up to Unique Paths. If you solved that problem, you already know how to fill a 2D DP table cell by cell. This problem adds one twist: obstacle cells contribute zero paths. That single change is all that separates "grid DP" from "grid DP with blocked cells."

Why this problem matters

Grids with obstacles show up constantly in interviews and real-world applications. Pathfinding through a map, routing around restricted zones, game boards with walls. The pattern is always the same: run the same DP as Unique Paths, but treat blocked cells as dead ends.

Once you see how a single if obstacle: dp = 0 handles the constraint, you can apply the same idea to any grid DP variant that introduces blocked or forbidden cells. The core building block does not change. You just add a guard.

The approach

The idea is identical to Unique Paths, with one rule added:

1. Define dp[r][c] as the number of unique paths to reach cell (r, c).
2. If grid[r][c] is an obstacle, set dp[r][c] = 0. No path can pass through a blocked cell.
3. Otherwise, dp[r][c] = dp[r-1][c] + dp[r][c-1] (paths from above plus paths from the left).
4. Base cases: first row and first column get 1, but once you hit an obstacle in that row or column, everything after it becomes 0 too (the robot cannot jump over obstacles).

That last point is the key insight people miss. In the obstacle-free version, the entire first row and first column are all 1s. With obstacles, an obstacle in row 0 blocks every cell to its right, and an obstacle in column 0 blocks every cell below it.

Walkthrough

Let's trace through the example grid [[0,0,0],[0,1,0],[0,0,0]] where 1 marks the obstacle at position (1,1):

The obstacle at (1,1) forces dp[1][1] = 0. That zero propagates through the table. Cells that would normally receive contributions from (1,1) get nothing from that direction, reducing the total path count.

Python solution

def unique_paths_with_obstacles(grid):
    rows, cols = len(grid), len(grid[0])
    if grid[0][0] == 1 or grid[rows - 1][cols - 1] == 1:
        return 0

    dp = [0] * cols
    dp[0] = 1

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                dp[c] = 0
            elif c > 0:
                dp[c] = dp[c] + dp[c - 1]

    return dp[cols - 1]

This is the space-optimized version from the start. There is no need to build the full 2D table when a single row is enough.

How the 1D DP works

The trick is the same one from Unique Paths and Minimum Path Sum. You maintain a single array dp of length n. As you process each row:

• Before you update dp[c], its value is the "from above" contribution (the value left over from the previous row).
• After you update dp[c-1], that value is the "from left" contribution for the current row.
• If grid[r][c] is an obstacle, you force dp[c] = 0 regardless of what the neighbors say.

Walk through the example row by row:

• Initialize: dp = [1, 0, 0]. Start cell is free, so dp[0] = 1.
• Row 0: c=0 is free, dp[0] stays 1. c=1 is free, dp[1] = dp[1] + dp[0] = 0 + 1 = 1. c=2 is free, dp[2] = dp[2] + dp[1] = 0 + 1 = 1. Row: [1, 1, 1].
• Row 1: c=0 is free, dp[0] stays 1. c=1 is an obstacle, dp[1] = 0. c=2 is free, dp[2] = dp[2] + dp[1] = 1 + 0 = 1. Row: [1, 0, 1].
• Row 2: c=0 is free, dp[0] stays 1. c=1 is free, dp[1] = dp[1] + dp[0] = 0 + 1 = 1. c=2 is free, dp[2] = dp[2] + dp[1] = 1 + 1 = 2. Row: [1, 1, 2].
• Return dp[2] = 2.

Complexity analysis

Time: O(m * n). You visit every cell exactly once.

Space: O(n). A single 1D array of length n. You do not need the full 2D table because each cell only depends on the cell above (previous row) and the cell to the left (current row).

This is the same complexity as Unique Paths. The obstacle check adds O(1) work per cell, so it does not change the asymptotic bounds.

Edge cases to watch for

• Obstacle at start or end: if grid[0][0] == 1 or grid[m-1][n-1] == 1, return 0 immediately. No path can begin or end on a blocked cell.
• Single cell: if the grid is 1x1 and the cell is free, return 1. If it is blocked, return 0.
• Entire row blocked: if every cell in a row has an obstacle, no path can reach any cell below that row. The DP handles this naturally since all values in that row become 0, and all subsequent rows inherit those zeros from above.
• Obstacle in the first row: everything to the right of the obstacle in row 0 becomes 0. The robot cannot go left, so it cannot get past the block.
• Obstacle in the first column: everything below the obstacle in column 0 becomes 0. Same reasoning.

The building blocks

This problem is built on one reusable pattern: grid DP with blocked cells. It takes the standard 2D grid DP pattern (fill a table where each cell depends on its top and left neighbors) and adds a guard: if the cell is blocked, set its value to 0.

The pattern generalizes easily:

• Counting paths: blocked cells get dp[r][c] = 0 (this problem)
• Minimizing cost: blocked cells get dp[r][c] = infinity so they never win the min
• Maximizing reward: blocked cells get dp[r][c] = -infinity so they never win the max

The same guard applies to any grid DP problem where certain cells are forbidden. The transition function stays the same. You just add one check before computing it.

From understanding to recall

You have seen the DP table, the space optimization, and how obstacles propagate zeros through the grid. The logic is clear. But producing this solution from scratch under interview pressure is a different skill than reading about it.

In an interview, you need to remember three things beyond standard grid DP: check for obstacles at start and end up front, zero out obstacle cells during the fill, and handle first-row and first-column obstacles correctly in the base cases. Those details are easy to forget when you are under time pressure.

Spaced repetition makes them automatic. You revisit this problem at increasing intervals, each time writing the obstacle guard and the 1D optimization from memory. After a few reps, you see a grid with obstacles and the entire pattern fires without hesitation.

Grid DP with blocked cells is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is a far more effective strategy than grinding problems randomly and hoping the patterns stick.

Related posts

• Unique Paths - The obstacle-free version, and the foundation for this problem
• Minimum Path Sum - Same grid DP structure, but minimizing cost instead of counting paths