Medium

Unique Paths II

LAB

Given a grid with 1 as obstacles and 0 as open cells, return the number of paths from top-left to bottom-right moving only down or right.

EXAMPLES

Example 1

Input
{
  "obstacleGrid": [
    [
      0,
      0,
      0
    ],
    [
      0,
      1,
      0
    ],
    [
      0,
      0,
      0
    ]
  ]
}

Output
2

FUNCTION SHAPE

obstacleGrid: intMatrix→int

SOLUTION NOTE

Add obstacle check - return 0 if cell is blocked.

Reveal reference solution +

pythonREFERENCE

def uniquePathsWithObstacles(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])

    @cache
    def dp(i, j):
        if i >= m or j >= n or grid[i][j] == 1:
            return 0
        if i == m - 1 and j == n - 1:
            return 1
        return dp(i + 1, j) + dp(i, j + 1)

    return dp(0, 0)

TimeO(m × n)

SpaceO(m × n)

Open on LeetCode ↗