< Back




63. Unique Paths II

We reuse the existing space in the input, for funsies. We could always create another memoization
table, but because we're leetcoding, let's be as efficient as possible. We're given an input grid,
and we're asked to find the number of unique paths but there's a catch - we have obstacles that
might prevent us from reaching the end.

First, we check to make sure our starting point and end points don't have obstacles covering them.
If not, we mark the end point as having 1 unique path to reach it - (m - 1, n - 1) is the end point.
Then, we preprocess the grid for both the last column and the last row.

For the last column and the last row, we check to make sure the current cell we're inspecting isn't
an obstacle. If it isn't we check to make sure the previous cell below or to the right has a valid
path to the end - meaning that cell equals 1. If so, we mark our cell as 1 as well - meaning it has
a valid path to the end. Otherwise, we mark it as 0 - no valid path to the end from this cell.

We begin to process the rest of the grid from (m - 2, n - 2) - the first cells that can access
memoized values from the bottom and right cells. If the current cell we're inspecting isn't an
obstacle, we add the number of unique paths from the bottom and right. Otherwise, we mark the
current cell as 0 - it's an obstacle so no unique paths exist from this cell to the end.

Eventually, at (0, 0), we'll have the number of unique paths from (0, 0) to the end.

The solution is as follows:


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

          if obstacleGrid[0][0] or obstacleGrid[m - 1][n - 1]:
              return 0

          obstacleGrid[m - 1][n - 1] = 1

          for i in range(m - 2, -1, -1):
              obstacleGrid[i][n - 1] = int(
                  not obstacleGrid[i][n - 1] and obstacleGrid[i + 1][n - 1]
              )

          for j in range(n - 2, -1, -1):
              obstacleGrid[m - 1][j] = int(
                  not obstacleGrid[m - 1][j] and obstacleGrid[m - 1][j + 1]
              )

          for i in range(m - 2, -1, -1):
              for j in range(n - 2, -1, -1):
                  if not obstacleGrid[i][j]:
                      obstacleGrid[i][j] = (
                          obstacleGrid[i + 1][j] + obstacleGrid[i][j + 1]
                      )
                  else:
                      obstacleGrid[i][j] = 0

          return obstacleGrid[0][0]


_ Time Complexity:

  O(m * n) - Where m is the number of rows, and n is the number of columns, this solution requires
  polynomial time to calculate the number of unique paths.

_ Space Complexity:

  O(1) - We reuse the existing space provided in the input.