Unique Paths II — Grid DP with Obstacles Every Interviewer Adds as a Follow-up

Problem Statement#

You are given an m x n integer array obstacleGrid where obstacleGrid[i][j] is 0 (free cell) or 1 (obstacle). A robot starts at the top-left corner (0, 0) and tries 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 do not pass through any obstacle cell.

Constraints:

• 1 <= m, n <= 100
• obstacleGrid[i][j] is 0 or 1

Example 1:

Input:  obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: Two paths avoid the center obstacle:
  Right -> Right -> Down -> Down
  Down -> Down -> Right -> Right

Example 2:

Input:  obstacleGrid = [[0,1],[0,0]]
Output: 1
Explanation: Only one path: Down -> Right.

Example 3:

Input:  obstacleGrid = [[1,0]]
Output: 0
Explanation: Start cell is blocked — no paths exist.

Why This Problem Matters#

Unique Paths II is the canonical follow-up Amazon and Google interviewers add immediately after you solve Unique Paths. The question looks almost identical on the surface — but obstacles introduce constraints that break naive initialization and force you to think carefully about edge cases.

What if the start cell is blocked? What if the end cell is blocked? What if an obstacle sits on the first row or column, cutting off the entire border from there forward?

This problem is a litmus test for whether you truly understand the DP structure or just memorized the recurrence. Candidates who only remember dp[i][j] = dp[i-1][j] + dp[i][j-1] get tripped up immediately by the obstacle-zeroing step. Candidates who understand why the border is initialized to 1 in the obstacle-free case know exactly how to adapt when an obstacle short-circuits the border propagation.

The obstacle-zeroing pattern also appears in Minimum Path Sum, Dungeon Game, and any grid DP where certain cells are illegal. Master it once, apply it everywhere.

The Core Insight#

Define dp[i][j] as the number of valid paths from (0, 0) to (i, j) that avoid all obstacles.

Obstacle rule: If obstacleGrid[i][j] == 1, then dp[i][j] = 0 unconditionally. No path passes through a blocked cell, regardless of how many paths reach its neighbors.

Base cases:

• dp[0][0] = 1 if start is free, 0 if blocked.
• First row: propagate dp[0][j] = dp[0][j-1] while cells are free. The moment an obstacle appears, that cell and all cells to its right become 0 (they are reachable only from the left along the first row, and the left is now blocked).
• First column: same logic — propagate 1 downward until an obstacle, then 0 for everything below.

Recurrence for interior cells:

if obstacleGrid[i][j] == 1:
    dp[i][j] = 0
else:
    dp[i][j] = dp[i-1][j] + dp[i][j-1]

The recurrence is identical to Unique Paths. The only difference is the explicit zero-out for obstacle cells.

Building the DP Solution#

Step 1 — Naive recursive (exponential, no obstacle handling):

def uniquePathsWithObstacles(grid):
    def dfs(i, j):
        if i < 0 or j < 0 or grid[i][j] == 1:
            return 0
        if i == 0 and j == 0:
            return 1
        return dfs(i-1, j) + dfs(i, j-1)
    m, n = len(grid), len(grid[0])
    return dfs(m-1, n-1)

Step 2 — Memoized recursion:

from functools import lru_cache
 
def uniquePathsWithObstacles(grid):
    m, n = len(grid), len(grid[0])
    @lru_cache(None)
    def dp(i, j):
        if i < 0 or j < 0 or grid[i][j] == 1:
            return 0
        if i == 0 and j == 0:
            return 1
        return dp(i-1, j) + dp(i, j-1)
    return dp(m-1, n-1)

Step 3 — Bottom-up 1D rolling array (optimal): See the Optimized Solution section below.

Visual Dry Run#

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

After first row initialization: dp = [1, 1, 1] (no obstacles in row 0)

Process row 1 (left to right):

• j=0: no obstacle — dp[0] stays 1 (only came from above)
• j=1: obstacle! — dp[1] = 0
• j=2: no obstacle — dp[2] = dp[2] + dp[1] = 1 + 0 = 1

After row 1: dp = [1, 0, 1]

Process row 2 (left to right):

• j=0: no obstacle — dp[0] stays 1
• j=1: no obstacle — dp[1] = dp[1] + dp[0] = 0 + 1 = 1
• j=2: no obstacle — dp[2] = dp[2] + dp[1] = 1 + 1 = 2

After row 2: dp = [1, 1, 2] → Answer: 2

Full 2D table for reference:

Optimized Solution#

Python#

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: list[list[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
 
        # Start is blocked — no paths exist at all
        if obstacleGrid[0][0] == 1:
            return 0
 
        dp = [0] * n
        dp[0] = 1  # one way to reach the start
 
        # Initialize first row: propagate 1 until the first obstacle, then 0
        for j in range(1, n):
            dp[j] = 0 if obstacleGrid[0][j] == 1 else dp[j - 1]
 
        # Process rows 1 through m-1
        for i in range(1, m):
            # First column: can only arrive from above
            dp[0] = 0 if obstacleGrid[i][0] == 1 else dp[0]
 
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    dp[j] = 0        # obstacle blocks this cell
                else:
                    dp[j] += dp[j - 1]  # from above + from left
 
        return dp[n - 1]

JavaScript#

var uniquePathsWithObstacles = function(obstacleGrid) {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
 
    if (obstacleGrid[0][0] === 1) return 0;
 
    const dp = new Array(n).fill(0);
    dp[0] = 1;
 
    // Initialize first row
    for (let j = 1; j < n; j++) {
        dp[j] = obstacleGrid[0][j] === 1 ? 0 : dp[j - 1];
    }
 
    for (let i = 1; i < m; i++) {
        // First column update
        dp[0] = obstacleGrid[i][0] === 1 ? 0 : dp[0];
 
        for (let j = 1; j < n; j++) {
            if (obstacleGrid[i][j] === 1) {
                dp[j] = 0;
            } else {
                dp[j] += dp[j - 1];
            }
        }
    }
 
    return dp[n - 1];
};

Complexity Analysis#

Common Mistakes#

1. Not returning 0 immediately when the start cell is blocked. If obstacleGrid[0][0] == 1, return 0 immediately. Failing to check sets dp[0] = 1 and propagates wrong values throughout the table.

2. Initializing the entire first row/column to 1 without checking for obstacles. In Unique Paths every border cell gets 1. With obstacles, the moment you hit a 1 in the first row or column, all subsequent cells in that line become 0. Copying the obstacle-free initialization verbatim misses this.

3. Forgetting to zero out obstacle cells in interior rows. The standard recurrence blindly adds two neighbors. You must explicitly set dp[j] = 0 when the current cell is an obstacle, not just skip the addition.

4. Wrapping around dp[j-1] when j == 0. When updating the first column (j == 0), there is no left neighbor. Some implementations compute dp[0] += dp[-1], which in Python wraps to the last element — a silent bug. Always handle the first column separately.

5. Not handling the end cell being blocked. If obstacleGrid[m-1][n-1] == 1, the answer is 0. With correct DP this is handled automatically (the end cell gets zeroed), but not testing this edge case reveals incomplete understanding.

6. Mutating the input grid without declaring it. Some O(1) solutions write DP values back into obstacleGrid directly. This works but destroys the caller's data. In an interview, always mention this trade-off explicitly and ask whether input mutation is acceptable.

Interview Tips#

• State the key difference immediately: "This is Unique Paths but any cell with a 1 becomes unreachable — dp[i][j] = 0 if it's an obstacle."
• Walk through the border initialization carefully. Interviewers specifically watch whether you short-circuit the first row/column correctly when an obstacle appears.
• Check edge cases aloud: start blocked (return 0), end blocked (return 0), single cell (return 1 - grid[0][0]).
• Offer the in-place option but immediately note that it mutates input — this shows you think about API contracts.
• For the follow-up "what if you want to reconstruct a path," say: "I would save the full 2D DP table and backtrack from the bottom-right corner toward (0,0), always moving toward a nonzero neighbor."

Follow-up Questions#

Q: What if the grid has costs at each cell instead of obstacles? (LC 64 Minimum Path Sum) Replace path counting with cost minimization: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Obstacles can be treated as cells with infinite cost.

Q: How do you find the number of paths modulo 10^9 + 7 for large grids? Same recurrence, but apply % (10**9 + 7) at each addition. Python handles this naturally; in C++/Java use long long intermediate values.

Q: What if the robot can also move up or left? 2D DP fails because dependencies become circular. You need DFS/BFS with a visited set or memoization that includes the visited state.

Q: Reconstruct any valid path. Fill the full 2D DP table. Backtrack from (m-1, n-1): at each step, move toward whichever of (i-1, j) or (i, j-1) has a nonzero dp value. Return the list of cells visited.

Q: What if new obstacles are added dynamically? Recompute the DP table after each update — O(mn) per update. For frequent queries, segment tree or 2D Fenwick tree approaches exist but are beyond standard interview scope.

Key Takeaways#

• The obstacle-zeroing rule is the entire extension: dp[i][j] = 0 when the cell is blocked; otherwise identical to Unique Paths.
• Border initialization is not trivially "all 1s" — once an obstacle appears on the first row or column, every cell beyond it in that line is also 0.
• Always check: start blocked? End blocked? Single-cell grid? These edge cases are designed to fail candidates who only know the happy-path recurrence.
• The 1D rolling array works identically here — zero out dp[j] for obstacles, add dp[j-1] for free cells.
• This problem is almost always asked as a follow-up to LC 62. Treat both as one topic and practice solving them back-to-back.
• Interviewers at Amazon and Google use this problem to test whether candidates truly understand DP invariants, not just recurrences.