Python Solution with comments


  • 0
    A
    class Solution:
        def uniquePathsWithObstacles(self, obstacleGrid):
            """
            :type obstacleGrid: List[List[int]]
            :rtype: int
            """
            """
            :type m: int
            :type n: int
            :rtype: int
            """
            # Here logic is same  current paths = top_paths + left_paths but the twist is now if we have block at that location then we need to set it to zero in order to block path from top and left
            m = len(obstacleGrid)
            n = len(obstacleGrid[0])
            memo = [[0]*n for elem in range(m)]
            # If source is blocked then no paths available else 1 for source
            if(obstacleGrid[0][0] == 1):
                return 0
            else:
                memo[0][0] = 1
            # If i == 0 and j == 0  continue for not setting up memo[i][j] again to zero
            # if obstacle present then set the current pos as zero else curr = left + top
            # and we are done
            for i in range(m):
                for j in range(n):
                    if(i == 0 and j == 0):
                        continue
                    if(obstacleGrid[i][j] != 1):
                        memo[i][j] = memo[i-1][j]+memo[i][j-1]
            return(memo[-1][-1])
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.