LeetCode 63: Unique Paths II

Problem Restatement

A robot starts at the top-left corner of a grid.

The robot wants to reach the bottom-right corner.

At each step, the robot may move only:

1. Right
2. Down

Some cells contain obstacles.

If a cell contains an obstacle, the robot cannot move onto that cell.

The grid uses:

0 = empty cell
1 = obstacle

We need to count how many unique valid paths exist.

The official constraints are 1 <= m, n <= 100. (leetcode.com)

Input and Output

Function shape:

def uniquePathsWithObstacles(
    obstacleGrid: list[list[int]]
) -> int:
    ...

Examples

For:

obstacleGrid = [
    [0,0,0],
    [0,1,0],
    [0,0,0],
]

The obstacle is in the center:

. . .
. X .
. . .

There are two valid paths:

Right -> Right -> Down -> Down
Down -> Down -> Right -> Right

So the answer is:

2

For:

obstacleGrid = [
    [0,1],
    [0,0],
]

The robot cannot move right from the start because of the obstacle.

Only one valid path exists:

Down -> Right

So the answer is:

1

First Thought: Recursive Search

A direct recursive approach is:

From each cell:

1. Move right
2. Move down

Stop when:

• We leave the grid
• We hit an obstacle

This works logically, but many recursive calls recompute the same cells repeatedly.

We need dynamic programming.

Key Insight

Without obstacles, the number of paths to a cell equals:

paths from above +
paths from left

The same idea still works here.

The only difference is:

If a cell is blocked, the number of paths to it is zero.

So:

if obstacle:
    dp[row][col] = 0
else:
    dp[row][col] =
        dp[row - 1][col] +
        dp[row][col - 1]

Base Cases

The start cell matters.

If the start cell is blocked:

obstacleGrid[0][0] == 1

then no path exists.

The first row and first column also need careful handling.

Once an obstacle appears in the first row, every cell after it becomes unreachable because the robot can only move right.

The same idea applies to the first column.

Algorithm

Create a DP table:

dp = [[0] * n for _ in range(m)]

If the start cell is blocked, return 0.

Otherwise:

dp[0][0] = 1

Then fill the table.

For each cell:

1. If it is an obstacle, set paths to 0.
2. Otherwise, add paths from above and left.

Return:

dp[m - 1][n - 1]

Correctness

The robot may move only right or down.

Therefore every path reaching cell (row, col) must come either from (row - 1, col) or (row, col - 1).

If (row, col) contains an obstacle, the robot cannot stand on that cell. So the number of paths to that cell must be zero.

Otherwise, every valid path to (row, col) comes from either above or left. These two sets of paths are disjoint because the final move differs. Therefore the total number of paths equals the sum of the number of paths from those two neighboring cells.

The algorithm initializes the starting cell correctly and fills the table row by row using already-correct earlier values. Therefore every DP value becomes correct, including the bottom-right corner.

Complexity

Implementation

class Solution:
    def uniquePathsWithObstacles(
        self,
        obstacleGrid: list[list[int]],
    ) -> int:

        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        dp = [[0] * n for _ in range(m)]

        if obstacleGrid[0][0] == 1:
            return 0

        dp[0][0] = 1

        for row in range(m):
            for col in range(n):
                if obstacleGrid[row][col] == 1:
                    dp[row][col] = 0

                else:
                    if row > 0:
                        dp[row][col] += dp[row - 1][col]

                    if col > 0:
                        dp[row][col] += dp[row][col - 1]

        return dp[m - 1][n - 1]

Code Explanation

First get the grid dimensions:

m = len(obstacleGrid)
n = len(obstacleGrid[0])

Create the DP table:

dp = [[0] * n for _ in range(m)]

If the starting cell is blocked, no path exists:

if obstacleGrid[0][0] == 1:
    return 0

Otherwise initialize:

dp[0][0] = 1

Now process every cell:

for row in range(m):
    for col in range(n):

If the current cell is blocked:

if obstacleGrid[row][col] == 1:
    dp[row][col] = 0

Otherwise, add paths from above:

if row > 0:
    dp[row][col] += dp[row - 1][col]

and from the left:

if col > 0:
    dp[row][col] += dp[row][col - 1]

Finally return:

return dp[m - 1][n - 1]

Space Optimization

We only need the current row.

So we can reduce space to O(n).

The transition becomes:

dp[col] += dp[col - 1]

If a cell contains an obstacle:

dp[col] = 0

Optimized Implementation

class Solution:
    def uniquePathsWithObstacles(
        self,
        obstacleGrid: list[list[int]],
    ) -> int:

        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        dp = [0] * n

        dp[0] = 1

        for row in range(m):
            for col in range(n):
                if obstacleGrid[row][col] == 1:
                    dp[col] = 0

                elif col > 0:
                    dp[col] += dp[col - 1]

        return dp[-1]

Testing

def run_tests():
    s = Solution()

    assert s.uniquePathsWithObstacles([
        [0,0,0],
        [0,1,0],
        [0,0,0],
    ]) == 2

    assert s.uniquePathsWithObstacles([
        [0,1],
        [0,0],
    ]) == 1

    assert s.uniquePathsWithObstacles([
        [1],
    ]) == 0

    assert s.uniquePathsWithObstacles([
        [0],
    ]) == 1

    assert s.uniquePathsWithObstacles([
        [0,0],
        [1,1],
        [0,0],
    ]) == 0

    assert s.uniquePathsWithObstacles([
        [0,0,0],
        [0,0,0],
    ]) == 3

    print("all tests passed")

run_tests()