Free lesson · DSA Mastery - Interview Prep, End to End

Unique Paths II

Hard12 min readdsadynamic-programming

Unique Paths II

Unique Paths II generalizes "count paths in a grid" to the case where some cells are obstacles: given an m × n grid with 0s for empty cells and 1s for obstacles, count the number of paths from the top-left to the bottom-right using only right and down moves, avoiding obstacles. The DP is dp[i][j] = dp[i-1][j] + dp[i][j-1] (paths from above plus paths from the left, exactly Pascal's recurrence rewritten for a grid), with the modification that dp[i][j] = 0 if cell (i, j) is an obstacle (no paths can pass through it). It introduces obstacle handling - zeroing out states that are forbidden - and shows that "count paths in a grid" is fundamentally the same recurrence as Pascal's triangle, just with a different geometry and the obstacle rule layered on top. We present the 2-D DP with obstacle zeroing (canonical) and the 1-D space-optimized version (optimal).

The insight: a path from (0, 0) to (i, j) ends with either a right move (from (i, j-1)) or a down move (from (i-1, j)), so the number of paths to (i, j) is the sum of paths to those two predecessors. Obstacles block paths: an obstacle at (i, j) means no path ends there, so dp[i][j] = 0. Combined: dp[i][j] = 0 if obstacle, else dp[i-1][j] + dp[i][j-1]. This is Pascal's recurrence on a grid with a "forbidden cells" overlay.

The Problem

You are given an m x n integer array obstacleGrid. There is a robot initially located at the top-left corner (i.e., obstacleGrid[0][0]). The robot tries to move to the bottom-right corner (i.e., obstacleGrid[m-1][n-1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in obstacleGrid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Example 1:

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

Explanation: There are two paths around the single obstacle in the middle.

Example 2:

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

Constraints:

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

Approaches Overview

#	Approach	Time	Space	Verdict
1	2-D path-counting DP with obstacle zeroing	O(m · n)	O(m · n)	Canonical
2	1-D space-optimized (single row)	O(m · n)	O(n)	Optimal

dp[i][j] = the number of unique paths from (0, 0) to (i, j). If (i, j) is an obstacle, dp[i][j] = 0. Otherwise dp[i][j] = dp[i-1][j] + dp[i][j-1]. Base case: dp[0][0] = 1 if not an obstacle, else 0 (no path even starts). First row and column propagate: each entry equals the previous one if the current cell is not an obstacle (otherwise 0). The 1-D optimization carries a single row, updated in place left-to-right (which is correct for this transition since dp[j-1] reads the just-updated current row's left neighbor and dp[j] reads the not-yet-updated previous row's same column).

Approach 1: 2-D Path-Counting DP - Canonical

The Idea

Define dp[i][j] = the number of paths from (0, 0) to (i, j). Base case: dp[0][0] = 1 if the start is not an obstacle (else 0, and the answer is 0). For the first row and column, each cell inherits from its single predecessor (if not an obstacle). For interior cells, dp[i][j] = dp[i-1][j] + dp[i][j-1] if (i, j) is open; otherwise dp[i][j] = 0. Fill row by row, left to right; return dp[m-1][n-1].

Logic Flowchart

graph TD
    A["dp[0][0] = 1 if open, else 0"] --> B["first row/col: dp[i][j] = dp[prev] if open, else 0"]
    B --> C["for each interior (i, j):"]
    C --> D{"obstacleGrid[i][j] == 1?"}
    D -->|Yes| E["dp[i][j] = 0  (path blocked)"]
    D -->|No| F["dp[i][j] = dp[i-1][j] + dp[i][j-1]  (above + left)"]
    E --> C
    F --> C
    C --> G["return dp[m-1][n-1]"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows Unique Paths II: a 2-D count table where obstacles zero out a cell and open cells sum the paths from above and from the left, returning the count at the bottom-right.

Code

public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
    int[][] dp = new int[m][n];
    if (obstacleGrid[0][0] == 1) return 0;                // start blocked → no paths
    dp[0][0] = 1;
    for (int j = 1; j < n; j++)                            // first row
        dp[0][j] = (obstacleGrid[0][j] == 1) ? 0 : dp[0][j - 1];
    for (int i = 1; i < m; i++)                            // first column
        dp[i][0] = (obstacleGrid[i][0] == 1) ? 0 : dp[i - 1][0];
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = (obstacleGrid[i][j] == 1) ? 0 : dp[i - 1][j] + dp[i][j - 1];
    return dp[m - 1][n - 1];
}

// Usage:
// uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]]) -> 2
// uniquePathsWithObstacles([[0,1],[0,0]]) -> 1

This Java code counts unique paths with obstacles: the count at each open cell sums the paths from above and from the left, while obstacles zero the cell, returning the count at the bottom-right.

Step-by-Step Walkthrough

Tracing uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]]):

graph LR
    F0["dp[0]: [1,1,1] (no obstacles)"]
    F1["dp[1]: dp[1][0]=1; dp[1][1]=0 (obstacle); dp[1][2]=dp[0][2]+dp[1][1]=1+0=1"]
    F2["dp[2]: dp[2][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"]
    F3["return 2"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough counts paths around the obstacle in a three-by-three grid: the obstacle in the middle blocks the direct route, leaving two paths - one going right then down twice, one going down twice then right.

Result: 2.

Complexity

Time: O(m · n) - one pass over the grid. Space: O(m · n) for the 2-D table.

Approach 2: 1-D Space-Optimized - Optimal

The Idea

Each row reads only from the previous row and the current row's left neighbor. So a single 1-D array suffices, updated in place left-to-right: when computing dp[j], dp[j] still holds the previous row's value (acts as dp[i-1][j]) and dp[j-1] already holds the current row's just-computed value (acts as dp[i][j-1]). Obstacles zero the cell directly.

Code

public static int uniquePathsWithObstaclesOptimized(int[][] obstacleGrid) {
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
    int[] dp = new int[n];
    dp[0] = (obstacleGrid[0][0] == 1) ? 0 : 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[i][j] == 1) dp[j] = 0;        // obstacle blocks paths
            else if (j > 0) dp[j] += dp[j - 1];            // dp[j] (above) + dp[j-1] (left, just updated)
            // j == 0 keeps its current value (paths from above), already 0 if blocked here or earlier
        }
    }
    return dp[n - 1];
}

// Usage: uniquePathsWithObstaclesOptimized([[0,0,0],[0,1,0],[0,0,0]]) -> 2

This Java code counts paths with obstacles using a single row updated left to right, with each open cell adding the left neighbor's count and obstacles zeroing the cell.

Complexity

Time: O(m · n). Space: O(n) - a single row.

Complexity Comparison

Approach	Time	Space	Key Idea
2-D DP	O(m · n)	O(m · n)	dp[i][j] = dp[i-1][j] + dp[i][j-1], zero on obstacle
1-D space-optimized	O(m · n)	O(n)	single row, left-to-right in place

Both count the same paths; the 1-D version saves space by reusing a single row. The structural lesson is obstacle handling - zero out forbidden cells so they contribute nothing to the count - layered on Pascal's path-counting recurrence. The same dp[i][j] = dp[i-1][j] + dp[i][j-1] from Pascal's triangle, with dp[i][j] = 0 if obstacle.

Variations & Follow-ups

How does this generalize Pascal's path counting, and why does the recurrence transfer?

Pascal's triangle counts paths in a triangular grid where each cell has two upper neighbors and the recurrence is dp[i][j] = dp[i-1][j-1] + dp[i-1][j]. Unique Paths counts paths in a rectangular grid where the robot moves right or down from (0, 0), and each cell (i, j) is reached from (i-1, j) (above) or (i, j-1) (left). The recurrence becomes dp[i][j] = dp[i-1][j] + dp[i][j-1]. The two recurrences look slightly different (the offsets are different), but they are the same idea: each cell's path count is the sum of paths into it from the two cells it can be reached from. The geometry of "valid predecessors" differs (upper-left and upper-right in Pascal's, above and left in Unique Paths), but the combining is identical: sum the predecessors. Indeed, the number of paths from (0, 0) to (i, j) in a clear grid is exactly the binomial coefficient C(i + j, i) - a Pascal's triangle entry. So Unique Paths is Pascal's path counting with rectangular geometry. The transferable principle: any "count paths in a grid under restricted moves" problem follows this recurrence shape, with the predecessors determined by the allowed move set. Right/down moves → above + left. Diagonal moves added → also upper-left. King moves on a chessboard → eight predecessors. Knight moves → eight specific offsets. The DP structure stays the same - sum over the predecessors - and only the predecessor set changes. Obstacles are an orthogonal modification: they zero out forbidden cells, blocking any path that would pass through them. The recurrence still applies to non-obstacle cells; obstacles just contribute 0 paths. This decomposition - recurrence from the move set + obstacle handling as a zero-out overlay - is a clean separation that scales: you can add obstacles to any path-counting DP without rederiving the recurrence. Recognizing "count paths under restricted moves with obstacles" as "Pascal-style path counting + obstacle zeroing" is the transferable pattern that lets you instantly write the DP for variants like grids with toll cells, weighted paths, or paths counted modulo a prime (modular arithmetic added on top).

Why does the 1-D in-place update work left-to-right (unlike the 0/1 knapsack)?

In the 0/1 knapsack 1-D optimization, we iterated capacity backward to prevent reusing an item. Here, the 1-D Unique Paths optimization iterates left-to-right - forward. Why the difference? In knapsack, the danger was that updating dp[c] with an item could then re-read the updated value for a larger capacity, double-counting the item. The backward loop prevented dp[c - w] from holding the just-updated (this-item) value when computing dp[c]. In Unique Paths, the analogous concern would be: when computing dp[j], does dp[j - 1] hold the previous row's value or the current row's just-updated value? The answer: it holds the current row's value (just computed), which is exactly what we want. The recurrence is dp[i][j] = dp[i-1][j] + dp[i][j-1] - the first term wants the previous row's value at column j (which is what dp[j] holds before its update), and the second term wants the current row's value at column j-1 (which is what dp[j-1] holds after its update). Left-to-right achieves both: when we reach column j, dp[j] still holds the previous row's value (giving us dp[i-1][j]), and dp[j-1] already holds this row's new value (giving us dp[i][j-1]). Computing dp[j] += dp[j-1] then sets dp[j] to its new value dp[i-1][j] + dp[i][j-1], perfectly. The general principle: the loop direction for a 1-D space-optimized DP depends on which cells the transition reads. For "above + left" (Unique Paths), left-to-right works because we want the new left and old above. For 0/1 knapsack's "exclude or include," we wanted the old dp[c-w] (to avoid reusing the item), so we iterated backward. Always check what the transition reads before choosing the loop direction. The wrong direction silently solves a different problem. Unique Paths II teaches the forward direction for "above + left" transitions, contrasting cleanly with knapsack's backward direction. This pattern - "carry one row, update in place in the right direction" - is the standard space optimization for grid DPs and recurs throughout the sub-group.

How does obstacle handling fit the broader DP technique, and where else does it appear?

Obstacles are a clean instance of zeroing out forbidden states - a recurring DP technique where some states are made unreachable (count 0) or invalid (-infinity / infinity sentinel for optimization), and the transitions naturally propagate this absence. Obstacles in grid paths: zero forbidden cells, and the path counts flowing through them vanish. Forbidden moves in step problems: mark forbidden positions as 0 reachability, and counts route around them. Excluded items in knapsack-like problems: treat them as "do not consider," which zeros their contribution. Trap squares in board games: zero or -infinity to make landing there a losing/forbidden state. The technique - represent forbiddenness as the absorbing element of the combining operator (0 for counting, -infinity for max, +infinity for min) - works because the operator naturally propagates it: 0 + anything = anything only sums real paths; an obstacle's 0 adds nothing to its neighbors' counts. Similarly, min(infinity, x) = x lets infinity sentinels for forbidden states never falsely improve the min. This use the operator's identity for absence idiom is broadly transferable. The lesson: when modeling "this state is forbidden / unreachable," set it to the operator's identity so transitions naturally handle it without special-casing. Combined with the path-counting recurrence, this gives Unique Paths II a clean and uniform DP: every cell uses the same if obstacle then 0 else combine pattern. The decomposition - recurrence + forbidden-state zeroing - extends to weighted paths (dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] for cost-minimizing grids), where obstacles can be modeled as infinity cells the min rejects, or to multi-objective grids with multiple overlays. Unique Paths II is the cleanest place to internalize this idiom on a counting DP.

How does Unique Paths II prepare for the rest of the grid-path family?

The grid-path family - Minimum Path Sum, Triangle, Max Points with Cost, Min Falling Path Sum, Dungeon Game, Cherry Pickup - all share Unique Paths II's skeleton with the operator and constraints varied. Minimum Path Sum (next topic) replaces the counting + with min and adds a cost per cell: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]. Same neighbors, same fill order; the operator is min, and each cell contributes a cost. Triangle uses a triangular shape with min (or max) over two diagonal neighbors. Max Points with Cost allows diagonal moves and minimizes a more complex objective. Min Falling Path Sum generalizes Min Path Sum to "from any top cell to any bottom cell, with three move options." Dungeon Game requires reasoning backward from the end (the bottom-right corner) because constraints depend on future costs. Cherry Pickup uses two simultaneous walkers, doubling the state to 4-D. Across all of them, the skeleton is the same as Unique Paths II - a 2-D dp[i][j], a neighbor-based transition, a row-by-row fill, obstacle/boundary handling - and the variations swap the operator (min/max/+) and the cost model. Unique Paths II is the cleanest counting instance with obstacles; subsequent topics shift to optimization and richer constraints. By internalizing the path-counting form with obstacle zeroing here, you have the template for every grid-path problem in the sub-group: change the operator, add per-cell costs, add or remove movement directions, and the DP adapts immediately. The recognition habit: when you see "from start to goal in a grid with restricted moves and some forbidden / costly cells," the answer is a grid-path DP with the right operator and the obstacle-zeroing or cost-adding overlay. Unique Paths II provides the foundation; the rest of the sub-group exercises the variations.

What about edge cases?

Start or end is an obstacle: Return 0 (no path can start or finish). The base-case check obstacleGrid[0][0] == 1 handles the start; the recurrence naturally gives dp[m-1][n-1] = 0 if the end is blocked.
First row or column has an obstacle: All cells beyond the obstacle in that row/column have count 0 (no path can route around within a 1-wide strip).
All-clear grid: Equivalent to standard Unique Paths; count is C(m + n - 2, m - 1).
All-obstacle grid or impossible layout: Count 0.
Single cell (m = n = 1): Count 1 if open, 0 if blocked.

Common Interview Pitfalls

Not handling obstacle at the start. obstacleGrid[0][0] == 1 immediately makes the count 0; check this before initializing.
First-row / first-column inheritance after an obstacle. Once an obstacle appears in the first row or column, all subsequent cells in that row/column must be 0 (no path reaches them along the strip).
Wrong loop direction in 1-D optimization. Left-to-right is correct here (reading old above + new left); a backward loop would solve the wrong problem.
Integer overflow. For m + n near 200, C(m + n - 2, m - 1) can be huge; the problem constraints fit in int for this size, but be careful with larger variants.

Why This Topic Matters

Unique Paths II is the canonical 2-D path-counting DP with obstacle handling: the recurrence dp[i][j] = dp[i-1][j] + dp[i][j-1] (Pascal's path counting on a grid) is layered with dp[i][j] = 0 if obstacle to zero out forbidden states. It teaches the forbidden-state zeroing idiom - set forbidden cells to the combining operator's identity (0 for counting, ±infinity for optimization) so the transitions naturally propagate absence - and demonstrates that grid-path counting is Pascal's recurrence with rectangular geometry. It also introduces the forward 1-D space optimization for "above + left" transitions, contrasting with the 0/1 knapsack's backward loop. The skeleton - 2-D state, neighbor-based transition, row-by-row fill, boundary handling, forbidden-state overlay - is the template for the entire grid-path family.

The next topic, Minimum Path Sum, switches the operator from counting to optimization: given an m × n grid of non-negative numbers, find a path from top-left to bottom-right (with only right/down moves) that minimizes the sum of values along the path. The DP is dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] - the same two-neighbor recurrence as Unique Paths, but with min replacing + and a per-cell cost added. It establishes the grid-path optimization skeleton (the model for nearly every grid-cost DP in the sub-group) and reinforces the count-vs-optimization operator fork on a 2-D state.

Back to DSA Mastery - Interview Prep, End to End