Unique Paths II (LeetCode 63)

The problem

You get an m × n grid of 0s and 1s, where 1 is an obstacle. A robot starts at the top-left cell and must reach the bottom-right cell, moving only right or down, and it can’t enter an obstacle. Return the number of possible paths.

Input:
0 0 0
0 1 0
0 0 0

Output: 2

The obstacle in the middle leaves two routes: along the top then down the right side, or down the left side then along the bottom.

How to think about it

Start with brute force. Recursively try right and down from every open cell, stopping at obstacles and walls. That is exponential, and it recounts the same cells from many routes, just like Unique Paths.

The key insight: an obstacle is a cell with zero paths. The recurrence doesn’t change. A free cell is still reached from above or from the left, so dp[i][j] = dp[i-1][j] + dp[i][j-1]. An obstacle cell simply has dp[i][j] = 0, which automatically stops any path from flowing through it.

Edges are no longer all 1s. In Unique Paths the first row and column were all 1. Here, an obstacle on the first row blocks everything to its right. Rather than special-casing the edges, start with dp = [1, 0, 0, …] and run the same loop for every row, including row 0. The first column only ever keeps its value from above, so one obstacle there zeros the rest of the column.

Which pattern is this? 2-D grid DP. The tell is “count paths in a grid with blocked cells”: same recurrence as Unique Paths, with zeros where you can’t stand.

Approach

1. If the start cell is blocked, return 0.
2. Make dp of length n, all zeros, with dp[0] = 1.
3. For each row, for each column j: if the cell is an obstacle, set dp[j] = 0; otherwise, if j > 0, add the left neighbour, dp[j] += dp[j-1].
4. Return dp[-1].

Solution

def unique_paths_ii(grid):
    if grid[0][0] == 1: return 0                  # blocked start: no paths
    n = len(grid[0]); dp = [0] * n; dp[0] = 1
    for row in grid:
        for j in range(n):
            if row[j] == 1: dp[j] = 0             # obstacle: nothing passes through
            elif j > 0: dp[j] += dp[j-1]          # above (old dp[j]) + left
    return dp[-1]
# unique_paths_ii([[0,0,0],[0,1,0],[0,0,0]]) -> 2

Dry run

On the example grid, the dp row after each grid row:

In row 1 the obstacle zeros dp[1], so the right cell only gets the 1 from above. The answer is dp[-1] = 2.

Complexity

• Time: O(m · n). Each cell is processed once.
• Space: O(n). One row of counts.

Edge cases and pitfalls

• Blocked start or blocked end returns 0. The end case falls out of the loop: its dp is set to 0.
• An obstacle on the first row or column blocks every cell beyond it on that edge. Hard-coding the edges to 1 is the usual bug.
• Single cell [[0]] returns 1 and [[1]] returns 0.
• Large counts fit in Python integers; in Java the problem guarantees a 32-bit result, but intermediate rows are still worth thinking about.

Related problems

• Unique Paths (LeetCode 62): the obstacle-free version of the same DP.
• Minimum Path Sum (LeetCode 64): right/down moves again, minimising cost.
• Dungeon Game (LeetCode 174): a harder grid DP that has to be filled from the bottom-right.