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)(0,0) to (m−1,n−1)(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, obstacleGrid: List[List[int]]) -> int:
        # if you start at an obstacle
        if obstacleGrid[0][0] == 1:
            return 0

        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        # for memoization
        lookup = {}

        def recursiveCall(x: int, y: int):

            # base case
            if x == m - 1 and y == n - 1:
                return 1

            # if already calculated
            if (x, y) in lookup:
                return lookup[(x, y)]

            # down (x + 1, y) and right (x, y + 1)

            # if blocked, return 0 paths to target
            down = 0
            right = 0

            # out of bounds check
            if x + 1 >= m or y >= n:
                pass
            # recursively solve
            elif obstacleGrid[x + 1][y] == 0:
                down = recursiveCall(x + 1, y)

            # out of bounds check
            if x >= m or y + 1 >= n:
                pass
            # recursively solve
            elif obstacleGrid[x][y + 1] == 0:
                right = recursiveCall(x, y + 1)

            # store the result
            lookup[(x + 1, y)] = down
            lookup[(x, y + 1)] = right

            # combine the answers
            lookup[(x, y)] = down + right

            # return the result
            return lookup[(x, y)]

        # begin recursion
        return recursiveCall(0, 0)

Complexity

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

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

And we are done.