UniquePathII.py

# Question link - https://leetcode.com/problems/unique-paths-ii/description/?envType=study-plan-v2&envId=top-interview-150

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # Sol2: Dynamic Solution 
        # Optimize to: O(N*M) , O(N)
        N , M = len(obstacleGrid) , len(obstacleGrid[0])
        dp = [0] * M #Row length
        dp[M-1] = 1 #Last value will be 1

        # Traverse the grid matrix in reverse 
        for r in reversed(range(N)):
            for c in reversed(range(M)):
                # condition for block
                if obstacleGrid[r][c]:
                    dp[c] = 0

                # For down -> out of bounce 
                elif c + 1 < M:
                    dp[c] = dp[c] + dp[c+1]
                # else:
                #     # Right 
                #     dp[c] = dp[c] + 0

        # return trhe result -> Count of paths 
        return dp[0]
        
        
        
        # Sol1 : Recursive solution 
        # Complexity : O(N*M), O(N*M)
        # N , M = len(obstacleGrid) , len(obstacleGrid[0])
        # dp = {(N-1 , M-1): 1}

        # # Recursive function 
        # def dfs(r , c):
        #     # Base case: Two cases -> 
        #     # 1) Block by Obstacle 
        #     # 2) Reaching out of bounce 
        #     if r == N or c == M or obstacleGrid[r][c]:
        #         return 0
        #     # If the value is cached
        #     if (r,c) in dp:
        #         return dp[(r,c)]

        #     # Recurrance relation -> Down , Up moves 
        #     dp[(r,c)] = dfs(r+1,c) + dfs(r , c+1)
        #     return dp[(r,c)]

        # # Function call 
        # return dfs(0,0)