63. Unique Paths II

Problem¶

Given a grid where 0 is open and 1 is blocked, count the paths from the top-left to the bottom-right using only right or down moves and never entering an obstacle.

grid = [[0,0,0],
        [0,1,0],
        [0,0,0]]
moves = right or down
output = 2

Key trick¶

Use one-dimensional dynamic programming: before updating dp[c] it represents paths from above, while dp[c - 1] represents paths from the left.

Trap¶

Set an obstacle's path count to zero; special sentinel values complicate initialization and can obscure the fact that unreachable cells also naturally have zero paths.

Why is it interesting?¶

It demonstrates how a two-dimensional recurrence can be compressed to one dimension by updating states in the correct order.

Python solution¶

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: list[list[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [0] * n
        dp[0] = 1

        for r in range(m):
            for c in range(n):
                if obstacleGrid[r][c] == 1:
                    # Obstacles cannot be reached.
                    dp[c] = 0
                elif c > 0:
                    # dp[c] is from above; dp[c - 1] is from the left.
                    dp[c] += dp[c - 1]

        return dp[-1]

Time complexity: \(O(mn)\).

Space complexity: \(O(n)\).

Comment on my solution¶

Your recurrence and \(O(n)\) space reduction are correct, and the implementation handles blocked endpoints and unreachable cells.

Using float("-inf") is unnecessary and mixes integers with floats. Both obstacles and unreachable cells should have zero paths, which allows the same recurrence to work without separate first-row and first-column initialization.

# Ideas:
# - dp[i][j] = number of path reaching (i,j)
# - transition: dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
# - maybe using float("-inf") when cell can't be reached
#   the dp transition will continue to work without any change
# - we can reduce space from O(mn) to O(n)

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: list[list[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [1] * n
        if obstacleGrid[0][0] == 1:
            dp[0] = float("-inf")
        for c in range(1,n):
            if obstacleGrid[0][c] == 1 or dp[c - 1] == float("-inf"):
                dp[c] = float("-inf")
        for r in range(1,m):
            if obstacleGrid[r][0] == 1 or dp[0] == float("-inf"):
                dp[0] = float("-inf")
            for c in range(1, n):
                if obstacleGrid[r][c]:
                    dp[c] = float("-inf")
                    continue
                total = 0
                if dp[c - 1] != float("-inf"):
                    total += dp[c-1]
                if dp[c] != float("-inf"):
                    total += dp[c]
                dp[c] = total

        return 0 if dp[-1] == float("-inf") else dp[-1]