Unique Paths II

Adding Obstacles to a Problem You Already Know

Unique Paths II looks almost identical to Unique Paths. One small change: obstacles. That single twist forces you to slow down, re-examine every assumption, and adapt the same DP pattern carefully. Interviewers love this problem precisely because it separates candidates who understand the pattern from those who just memorized it.

Problem Statement

You are given an m × n grid called obstacleGrid.

• obstacleGrid[i][j] == 1 represents an obstacle.

• obstacleGrid[i][j] == 0 represents a free cell.

A robot starts at the top-left corner (0, 0) and wants to reach the bottom-right corner (m-1, n-1).

The robot can only move right or down.

Return the number of unique paths that avoid all obstacles.

1. Clarify Requirements Before Jumping Into Code

Before touching code, let's lock down the rules.

Input: A 2D integer grid where cells are either 0 (free) or 1 (blocked).

Output: Number of valid paths from top-left to bottom-right.

Constraints: Move right or down only. Cannot step on obstacles.

The edge cases here are more interesting than in Unique Paths.

• What if the starting cell (0,0) is blocked? Answer is immediately 0.

• What if the destination cell is blocked? Answer is immediately 0.

• What if an obstacle cuts across the only path through a narrow grid, like a single-row or single-column grids with an obstacle in the middle? Our answer is 0, but we can't determine that immediately.

Say these out loud in an interview. It demonstrates that you're thinking about the problem, not rushing to write code.

2. Identify the Category of the Problem

This is still grid-based, path-counting DP, the same category as Unique Paths. The structure is identical: define a state per cell, find a recurrence, then build up answers from base cases.

The difference is that some states are now invalid. But obstacles don't change the kind of problem. They simply add a conditional to the transition.

That's an important mental model: obstacles don't necessarily require a new algorithm, they may simply require a careful amendment to the one you already have.

3. Start With Brute Force to Build Intuition

The recursive approach mirrors what we did in Unique Paths: at each cell, try going right and going down, then sum the results. The only addition is: if you land on an obstacle, return 0 immediately.

int countPaths(int i, int j, int[][] grid) {
    if (i >= grid.length || j >= grid[0].length) 
        return 0; // out of bounds
    if (grid[i][j] == 1) 
        return 0; // obstacle
    if (i == grid.length - 1 && j == grid[0].length - 1) 
        return 1;  // destination

    return countPaths(i + 1, j, grid) + countPaths(i, j + 1, grid);
}

This correctly handles obstacles by returning 0 whenever one is hit. But our problem is the same as before: overlapping subproblems cause exponential time.

While our brute-force solution is not a realistic option, it does give us one key insight: an obstacle is just a cell that always contributes 0 paths. We'll carry that forward into the DP solution.

4. Brainstorm More Solutions

Step 1: Can We Just Add One Line to the Unique Paths Solution?

First, recall our Unique Paths recurrence:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Our first instinct might be to just skip the cell if it's an obstacle. But let's think carefully about whether that's right.

If we simply skip updating a cell when it's an obstacle, what happens? The cell retains whatever value it had before, which might be a nonzero value left over from a previous row.

That would be wrong. An obstacle cell should contribute zero paths, not some stale value.

So the correction isn't to skip. It's to explicitly zero out obstacle cells:

if (grid[i][j] == 1):
    dp[i][j] = 0
else:
    dp[i][j] = dp[i-1][j] + dp[i][j-1]

This small distinction matters a lot. Get it wrong and our solution may pass simple cases but fail on grids where obstacles appear after previously-visited cells.

Step 2: Reexamine Our Base Cases

In Unique Paths, we were able to set the first row and column to all 1s as our base case, since there's exactly one way to reach every cell in a straight line. Here, that logic breaks as soon as you hit an obstacle.

Consider this first row:

[0, 0, 1, 0, 0]

Cells 0 and 1 are reachable while Cell 2 is blocked.

But here's the critical point: cells 3 and 4 are also unreachable, even though they're free.

If we initialize the entire first row to 1 (like we did in Unique Paths) and then zero out the obstacle, cells 3 and 4 stay incorrectly set to 1.

How do we fix this? Simple - once we hit an obstacle while initializing the first row, everything after it must be 0. The same logic applies when initializing the first column going down.

Step 3: Full 2D DP

Now let's build the complete 2D solution. We define:

dp[i][j] = number of paths to reach (i, j) without hitting obstacles

Our logic for each cell:

• If grid[i][j] == 1: dp[i][j] = 0

• Otherwise: dp[i][j] = dp[i-1][j] + dp[i][j-1]

Let's trace a concrete example with this grid:

0  0  0
0  1  0
0  0  0

We can initialize the first row of our dp array as: [1, 1, 1]

And similarly set the first column to all 1's as well.

Then we can fill in the remaining cells:

dp[1][1]: obstacle → 0
dp[1][2]: dp[0][2] + dp[1][1] = 1 + 0 = 1

dp[2][1]: dp[1][1] + dp[2][0] = 0 + 1 = 1
dp[2][2]: dp[1][2] + dp[2][1] = 1 + 1 = 2

Our final grid looks like:

1  1  1
1  0  1
1  1  2

Solution: 2.

Time Complexity: O(m × n)

Space Complexity: O(m × n)

Step 4: Optimize to 1D

The same space optimization from Unique Paths also applies here. We only need to track a single row at a time, since each cell only looks one row up and one column left. That means we can process left to right and update in place:

dp[j] = dp[j] + dp[j-1]

// dp[j] (before it's updated) counts "paths from above" 
// dp[j-1] (already been updated) counts "paths from the left."

When we hit an obstacle, we zero out dp[j]. This naturally propagates forward. Any cell to the right of a zeroed obstacle will only accumulate the paths that flow around it.

Let's trace the same 3×3 grid with the 1D approach:

Initialize: dp = [1, 1, 1]   ← first row

Row 1 (i=1):
  j=0: grid[1][0]=0, j=0 so skip left contribution. dp[0] stays 1.
  j=1: obstacle! dp[1] = 0  →  dp = [1, 0, 1]
  j=2: dp[2] = dp[2] + dp[1] = 1 + 0 = 1  →  dp = [1, 0, 1]

Row 2 (i=2):
  j=0: grid[2][0]=0, j=0 so dp[0] stays 1.
  j=1: dp[1] = dp[1] + dp[0] = 0 + 1 = 1  →  dp = [1, 1, 1]
  j=2: dp[2] = dp[2] + dp[1] = 1 + 1 = 2  →  dp = [1, 1, 2]

Answer: dp[2] = 2 ✓

Notice how zeroing dp[1] at the obstacle correctly starved paths from flowing through it, but paths that go around it still accumulate normally.

Time Complexity: O(m × n)

Space Complexity: O(n)

5. Trade-Offs at a Glance

Approach	Time	Space	Notes
Brute-force recursion	O(2^(m+n))	O(m+n)	Too slow; great for intuition
Memoized recursion	O(m × n)	O(m × n)	Intuitive; stack overhead
2D bottom-up DP	O(m × n)	O(m × n)	Easiest to trace and debug
1D optimized DP	O(m × n)	O(n)	Best general solution

Note that there's no combinatorics shortcut here like in Unique Paths. Obstacles break the symmetry that made the math clean. DP is the right tool.

6. Pseudocode

if start cell is obstacle:
    return 0

initialize dp array of size n, all 0s
dp[0] = 1

for each row i from 0 to m-1:
    for each column j from 0 to n-1:
        if obstacle at (i, j):
            dp[j] = 0
        else if j > 0:
            dp[j] = dp[j] + dp[j-1]

return dp[n-1]

Notice that the loop starts at row 0 (unlike Unique Paths where we skipped it). That's because we need the obstacle check to run even on the first row. We can't just initialize everything to 1.

7. Consider Edge Cases

I explicitly check:

• Start or end cell blocked

• Single-row or single-column grids

• Obstacles that block the only possible path

The DP logic handles these naturally when initialized correctly.

8. Full Solution

public class UniquePathsII {

    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        // If start or end is blocked, no path exists
        if (obstacleGrid[0][0] == 1 || 
                obstacleGrid[m-1][n-1] == 1) {
            return 0;
        }

        int[] dp = new int[n];
        dp[0] = 1;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    // obstacle: zero out this cell
                    dp[j] = 0; 
                } else if (j > 0) {
                    // free cell: add paths from left
                    dp[j] = dp[j] + dp[j - 1];  
                }
            }
        }

        return dp[n - 1];
    }
}

9. Test Your Solution

// Standard case with center obstacle — answer: 2
System.out.println(uniquePathsWithObstacles(new int[][]{
    {0, 0, 0},
    {0, 1, 0},
    {0, 0, 0}
}));

// Blocked start — answer: 0
System.out.println(uniquePathsWithObstacles(new int[][]{{1}}));

// Single free cell — answer: 1
System.out.println(uniquePathsWithObstacles(new int[][]{{0}}));

// Obstacle forces one narrow path — answer: 1
System.out.println(uniquePathsWithObstacles(new int[][]{
    {0, 1},
    {0, 0}
}));

// Obstacle blocks all paths — answer: 0
System.out.println(uniquePathsWithObstacles(new int[][]{
    {0, 0},
    {1, 1}
}));

// Obstacle in first row — tests base case propagation — answer: 1
System.out.println(uniquePathsWithObstacles(new int[][]{
    {0, 0, 1, 0},
    {0, 0, 0, 0}
}));

That last test is important. It forces you to verify that an obstacle in the first row correctly zeros out everything to its right, the most common mistake candidates make on this problem.

10. Key Lessons for Future Problems

• Obstacles don't necessarily require a new algorithm. They often require a careful amendment. The DP structure is identical to Unique Paths. All that changed is one conditional in the transition and tighter attention to base cases.

• Be mindful of how invalid states propagate through your solution. Any time a cell represents an impossible or forbidden state in a DP problem, it should hold 0. Our solution ensures that zero naturally propagates: downstream cells won't count paths through the blocked cell.

• Base cases can hide the trickiest bugs. The first row and column logic is where many candidates go wrong on this problem. When a constraint (like an obstacle) can invalidate a base case, you can't pre-fill your array and forget about it.

• Trace your solution manually on a small example. Before writing code, walking through a 3×3 grid with a center obstacle takes 60 seconds and can help you catch potential bugs. Interviewers notice when you do this.

• Understand the pattern, don't memorize the code. If you understand why each piece of the solution works - why we zero out obstacles, why the 1D update works in-place, why the first row needs special handling - you can reconstruct this solution under pressure and adapt it to variations you've never seen.

Good Luck and Happy Coding!