Unique Paths II medium

Problem Statement

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (0, 0). The robot tries to move to the bottom-right corner (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 and 0 respectively in the grid.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner from the top-left corner without encountering any obstacles.

If there is no path, return 0.

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 and the total number of unique paths are 2.

Example 2:

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

Steps

1. Handle Base Cases: If the starting cell or the ending cell has an obstacle (value 1), there are no paths. Return 0.

2. Dynamic Programming: Create a DP table (matrix) of the same size as the input grid. Initialize the DP table. If there is an obstacle at (i, j) in the grid, set dp[i][j] = 0. Otherwise, if it is the starting cell (0, 0), set dp[0][0] = 1. For the first row and column, if there is no obstacle, the number of paths is 1 (only one way to reach those cells).

3. Iterate and Fill DP Table: Iterate through the DP table, starting from (1, 1). For each cell dp[i][j], the number of paths to reach it is the sum of paths from the cell above (dp[i-1][j]) and the cell to the left (dp[i][j-1]). However, if there is an obstacle at (i,j), dp[i][j] remains 0.

4. Return Result: The value at dp[m-1][n-1] (bottom-right corner) represents the total number of unique paths.

Explanation

The dynamic programming approach efficiently solves this problem by breaking it down into smaller subproblems. Each cell in the DP table stores the number of ways to reach that cell. By considering only the paths from the cells above and to the left, we avoid redundant calculations and ensure we count each path only once. The obstacle handling is seamlessly integrated into the DP logic by setting the value to 0 whenever an obstacle is encountered.

Code

def uniquePathsWithObstacles(obstacleGrid):
    """
    Finds the number of unique paths in a grid with obstacles.

    Args:
        obstacleGrid: A list of lists representing the grid.

    Returns:
        The number of unique paths.
    """
    m = len(obstacleGrid)
    n = len(obstacleGrid[0])

    # Handle base cases
    if obstacleGrid[0][0] == 1 or obstacleGrid[m - 1][n - 1] == 1:
        return 0

    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1

    # Initialize first row and column
    for i in range(1, m):
        if obstacleGrid[i][0] == 0:
            dp[i][0] = dp[i - 1][0]
    for j in range(1, n):
        if obstacleGrid[0][j] == 0:
            dp[0][j] = dp[0][j - 1]

    # Fill the DP table
    for i in range(1, m):
        for j in range(1, n):
            if obstacleGrid[i][j] == 0:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    return dp[m - 1][n - 1]

Complexity

• Time Complexity: O(m*n), where 'm' and 'n' are the dimensions of the grid. We iterate through the DP table once.
• Space Complexity: O(m*n), due to the DP table we create. We could optimize this to O(min(m,n)) by using only a 1D array if needed.