Problem Statement in English

You’re given an obstacle grid, obstacleGrid. You can’t use co-ordinates that have a value of 1, because they contain obstacles.

Your task is to calculate the number of paths from the origin $(0,0)$ to $(m - 1,n - 1)$.

Approach

This is simply an extension of a previously solved problem. We just add an extra check to see if we can use the co-ordinate or not (check for obstacles).

Solution in Python


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

        if grid[m - 1][n - 1] == 1 or grid[0][0] == 1: return 0

        @cache
        def dp(i, j):
            if i == m - 1 and j == n - 1:
                return 1

            res = 0
            
            if i + 1 < m and grid[i + 1][j] == 0:
                res += dp(i + 1, j)
            if j + 1 < n and grid[i][j + 1] == 0:
                res += dp(i, j + 1)

            return res

        return dp(0, 0)

Complexity

  • Time: $O(m \times n)$
    Since we iterate over $m \times n$ co-ordinates at most.

  • Space: $O(m \times n)$
    Since we might cache upto $m \times n$ values in the lookup table.

And we are done.