23 Oct 2025•Python•Medium

Unique Paths II

count paths from top-left to bottom-right with obstacles using dp with space optimization to O(n).

View original LeetCode question

use 1d dp array to track paths for current row. initialize dp[0] = 1 if start is not obstacle, else 0. for each row, if cell is obstacle, set dp[c] = 0. otherwise, dp[c] += dp[c-1] (paths from left).

for first column (c=0), only update from top (previous dp[0]). for other columns, add paths from left. space optimized from O(mn) to O(n) by processing row by row.

optimization

since we only need previous row values, use single array and update in-place. obstacle cells reset path count to 0.

complexity

O(mn) time, O(n) space where m and n are grid dimensions. efficient space-optimized dp.

Solution files

Python•unique-paths-ii/solution.py
from typing import List


class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if not obstacleGrid or not obstacleGrid[class="syntax-number">0]:
            return class="syntax-number">0

        rows, cols = len(obstacleGrid), len(obstacleGrid[class="syntax-number">0])
        dp = [class="syntax-number">0] * cols
        dp[class="syntax-number">0] = class="syntax-number">0 if obstacleGrid[class="syntax-number">0][class="syntax-number">0] == class="syntax-number">1 else class="syntax-number">1

        for r in range(rows):
            for c in range(cols):
                if obstacleGrid[r][c] == class="syntax-number">1:
                    dp[c] = class="syntax-number">0
                    continue

                if c == class="syntax-number">0:
                    continue

                dp[c] += dp[c - class="syntax-number">1]

        return dp[-class="syntax-number">1]