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.