LC 0063 [M] Unique Paths II - ALawliet/algorithms GitHub Wiki

prereq: unique paths 1

---

just like Unique Paths 1 but with the case that the num paths of an obstacle cell is 0

for the forward solution we prefill with the previous cell instead of just assuming 1 like Unique Paths I because there are obstacles that 0 out that current cell and the cells that come after:

ans no obs:  [6,3,1]
             [3,2,1]
             [1,1,1]

obs grid:    [0,0,0]
             [0,1,0]
             [0,0,0]

ans w/ obs:  [2,1,1]
             [1,0,1]
             [1,1,1]

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        n_rows = len(obstacleGrid)
        n_cols = len(obstacleGrid[0])
        
        T = [ [0 for _ in range(n_cols)] for _ in range(n_rows) ]
        
        if obstacleGrid[0][0] != 1: #
            T[0][0] = 1
        for r in range(1, n_rows):
            if obstacleGrid[r][0] != 1: #
                T[r][0] = T[r-1][0] #
        for c in range(1, n_cols):
            if obstacleGrid[0][c] != 1: #
                T[0][c] = T[0][c-1] #
            
        for r in range(1, n_rows):
            for c in range(1, n_cols):
                if obstacleGrid[r][c] != 1: #
                    T[r][c] = T[r][c-1] + T[r-1][c]
                
        return T[-1][-1]

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

            T = [ [0 for _ in range(n_cols + 1)] for _ in range(n_rows + 1) ]

            if obstacleGrid[n_rows-1][n_cols-1] != 1: # prefill if not an obstacle
                T[n_rows-1][n_cols-1] = 1

            for r in range(n_rows - 1, -1, -1):
                for c in range(n_cols - 1, -1, -1):
                    if obstacleGrid[r][c] != 1: # build path if not an obstacle
                        T[r][c] += T[r+1][c] + T[r][c+1]

            return T[0][0]

T/S: O(n_rows * n_cols)