This problem is relatively easy after solving the Unique Paths I problem, it just builds on the same problem by now adding obstacles to the grid. So I had to change the approach a bit. For the recursive approach, it was a matter of just adding more constraints. So, if the index was an index where there is an obstacle it would return 0. The time complexity for this approach is O(nm) and the space complexity is O(nm).

Note that in this problem the end index can also be an obstacle, in which case we can just return 0 right away in constant time and space.

Recursive Approach

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # T: O(nm) S: O(nm)
        ROWS, COLS = len(obstacleGrid), len(obstacleGrid[0])
        memo = {}
        end = ROWS-1, COLS-1
        def uP2(r, c):
            if (r >= ROWS or 
                c >= COLS or
                obstacleGrid[r][c] == 1):
                return 0
            if (r, c) == end: return 1 # this is second because end could be an obstacle
            if (r, c) not in memo:
                memo[(r, c)] = uP2(r+1, c) + uP2(r, c+1)
            return memo[(r, c)]
        return uP2(0, 0)

Iterative Approach

This approach is a lot different and is not as clean as it is in the Unique Paths I problem.

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # T: O(nm) S: O(nm), but we use obstacleGrid as our dp table
        if obstacleGrid[-1][-1] == 1: return 0 # if end is unreachable return 0
        ROWS, COLS = len(obstacleGrid), len(obstacleGrid[0])

        for r in range(ROWS):
            for c in range(COLS):
                obstacleGrid[r][c] = 1 if obstacleGrid[r][c] != 1 else 0
                
        for r in reversed(range(ROWS)):
            for c in reversed(range(COLS)):
                if (r, c) == (ROWS-1, COLS-1): continue # don't touch end index
                if obstacleGrid[r][c] == 1:
                    bottom = obstacleGrid[r+1][c] if r+1 < ROWS else 0
                    right = obstacleGrid[r][c+1] if c+1 < COLS else 0
                    obstacleGrid[r][c] = right + bottom
        return obstacleGrid[0][0]

To really reduce the space complexity as much as possible I converted the obstacleGrid into my dp table.

First, I iterate through the obstacleGrid and set every value which is not an obstacle to 1 and the obstacle to 0. Next, we iterate through all the indices, we make sure to ignore our end index. For all the indices which have value 1 (hence are not an obstacle) we check unique ways for the right and bottom indices, and if either is out of bound we set it to 0. The sum of the values would be the unique ways to reach the end for the current index. Finally, we return the value of 0, 0 index as our answer.

The time complexity for this approach is O(nm), and we could argue that the space complexity is constant since we are only manipulating the input grid.