LeetCode #63 Medium

Unique Paths II

Count right/down paths from top-left to bottom-right on a grid with obstacle cells.

dynamic-programmingmatrixgrid

02

Intuition

💡

Plain Unique Paths seeds the entire first row and first column with 1s before filling the interior. Copy that habit here and it silently produces wrong answers: an obstacle in the first row or column blocks everything BEHIND it too, since a path can't walk through it to reach cells further along that row or column. The seeding has to stop dead at the first obstacle, not run to the edge assuming a clear line. There's also a degenerate case the seeding trick hides: if the start cell itself is an obstacle, the answer is 0 immediately, no DP required.

03

Approach

1

Handle a blocked start

If grid[0][0] is 1, no path can even begin; return 0 immediately without building a DP table.

2

Fill with obstacle-aware transitions

Build dp the same shape as grid. Set dp[0][0] = 1. For every other cell, if it's an obstacle set dp[cell] = 0 outright. Otherwise sum the ways in from above and from the left, treating an out-of-bounds or obstacle neighbor as contributing 0. Because an obstacle's dp value is forced to 0, that 0 naturally propagates forward and stops the first row or column from continuing past it, without special-casing row 0 or column 0 separately.

3

Read the bottom-right corner

dp[R-1][C-1] holds the total path count avoiding every obstacle; if that cell is itself an obstacle it will correctly be 0.

04

Solution & live demo

python

▶1class Solution:
▶2    def uniquePathsWithObstacles(self, obstacleGrid: list[list[int]]) -> int:
▶3        R, C = len(obstacleGrid), len(obstacleGrid[0])
▶4        if obstacleGrid[0][0] == 1:
▶5            return 0
▶6        dp = [[0] * C for _ in range(R)]
▶7        dp[0][0] = 1
▶8        for i in range(R):
▶9            for j in range(C):
▶10                if i == 0 and j == 0:
▶11                    continue
▶12                if obstacleGrid[i][j] == 1:
▶13                    dp[i][j] = 0
▶14                    continue
▶15                top = dp[i - 1][j] if i > 0 else 0
▶16                left = dp[i][j - 1] if j > 0 else 0
▶17                dp[i][j] = top + left
▶18        return dp[R - 1][C - 1]

05

Edge cases

Start cell is an obstacle

Return 0 immediately, since a path needs a first step that doesn't exist.

Obstacle blocking the entire first row

Every cell after it in that row inherits dp = 0 from the top contribution being 0 and the left contribution chaining through the blocked cell.

Destination cell is an obstacle

dp[R-1][C-1] is forced to 0 during the fill, correctly reporting no valid path.

1x1 grid with no obstacle

dp[0][0] = 1 and that is also the destination, so the answer is 1 with no fill loop needed.

06

Complexity

Time

O(R*C)

Space

O(R*C), reducible to O(C) with a rolling row

Single pass over the grid, each cell computed once.