63. Unique Paths II

Approach 1: Dynamic Programming

As in Unique Paths I (which I very strongly recommend reading before this), we will initialize a 2-D array with 1's. There is a small edge case that we have to handle here since there are obstacles, which is that if there are obstacles in the first row, then we won't be able to reach any of the positions to the right of it. Similarly if there is an obstacle in the first column then we won't be able to reach any of the positions below it.

Once we accommodate those, all we have to do when iterating through the path matrix is to make sure our position is not an obstacle. If it is an obstacle then we have to make dp[i][j] for that position 0 since we can never reach an obstacle.

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        https://leetcode.com/problems/unique-paths-ii/description/
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[1]*n for _ in range(m)]
        for i in range(m):
            if obstacleGrid[i][0] == 1:
                for ix in range(i,m):
                    dp[ix][0] = 0
                break;
        for j in range(n):
            if obstacleGrid[0][j] == 1:
                for jx in range(j,n):
                    dp[0][jx] = 0
                break;
        for i in range(1,m):
            for j in range(1,n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

Time Complexity: O(m*n)

Space Complexity: O(m*n)