63.Unique_Paths_II(Medium).md

63. Unique Paths II (Medium)

Date and Time: Jan 31, 2025, 22:47 (EST)

Link: https://leetcode.com/problems/unique-paths-ii

Question:

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 10^9.

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

Output: 2

Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:

1. Right -> Right -> Down -> Down
   
2. Down -> Down -> Right -> Right

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]

Output: 1

Edge Case:

Input: obstacleGrid = [[1,0]]

Output: 0

Edge Case:

Input: obstacleGrid = [[1],[0]]

Output: 0

Edge Case:

Input: obstacleGrid = [[0,1,0,0]]

Output: 0

Constraints:

• m == obstacleGrid.length

• n == obstacleGrid[i].length

• 1 <= m, n <= 100

• obstacleGrid[i][j] is 0 or 1.

Walk-through:

1. Base case: check the starting postion if this is 1, if so, that means we have no way to reach the end, so we should return 0. Otherwise, set starting position to 1.

2. Fill out the base case for the first row and the first column. We check if current grid is 1, if so, we should set this grid to be 0. Else, we should set current grid to either its previous row or previous col.

3. Fill out the rest by this recurrence relation dp[r][c] = dp[r-1][c] + dp[r][c-1]. We also need to check if current obstacleGrid[r][c] == 1 or not, if so, we should set it to be 0.

4. Finally, return the last grid of obstacleGrid.

Python Solution:

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # dp: how many ways to reach, dp[r][c] = dp[r-1][c] + dp[r][c-1], if grid is obstacle, set to 0
        # Check starting pos is 1 or not, if so, return 0. Otherwise, set it to be 1

        # TC: O(m*n), m=rows, n=cols, SC: O(1)
        rows, cols = len(obstacleGrid), len(obstacleGrid[0])
        # Base case
        if obstacleGrid[0][0] == 1:
            return 0
        obstacleGrid[0][0] = 1
        for c in range(1, cols):
            # If current pos is obstacle, set to 0
            if obstacleGrid[0][c] == 1:
                obstacleGrid[0][c] = 0
            # Otherwise, take its previous col
            else:
                obstacleGrid[0][c] = obstacleGrid[0][c-1]
        for r in range(1, rows):
            if obstacleGrid[r][0] == 1:
                obstacleGrid[r][0] = 0
            else:
                obstacleGrid[r][0] = obstacleGrid[r-1][0]

        # Fill out the rest
        for r in range(1, rows):
            for c in range(1, cols):
                # If is obstacle, set to 0
                if obstacleGrid[r][c] == 1:
                    obstacleGrid[r][c] = 0
                # Else sets to the sum of left, up neighbors
                else:
                    obstacleGrid[r][c] = obstacleGrid[r-1][c] + obstacleGrid[r][c-1]
            
        return obstacleGrid[-1][-1]

Time Complexity: $O(m*n)$
Space Complexity: $O(1)$