Unique Paths II

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.

For example, given the input obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]], the expected output is 2. As another example, given obstacleGrid = [[0,1],[0,0]], the expected output is 1.

# Unique Paths with Obstacles

## Problem Description

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*.


**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

## Brute Force Approach (Not Recommended)

A brute-force approach would involve exploring all possible paths from the top-left corner to the bottom-right corner using recursion.  However, this approach is highly inefficient due to overlapping subproblems, leading to exponential time complexity.

## Optimal Solution: Dynamic Programming

We can use dynamic programming to solve this problem efficiently. We'll create a 2D array `dp` of the same size as the input grid `obstacleGrid`. `dp[i][j]` will store the number of unique paths to reach cell `(i, j)`. 

**Algorithm:**

1.  Initialize the first cell `dp[0][0]`. If `obstacleGrid[0][0]` is 0, then `dp[0][0] = 1`; otherwise, `dp[0][0] = 0`.
2.  Iterate through the first row. If `obstacleGrid[0][j]` is 0, then `dp[0][j] = dp[0][j-1]`; otherwise, `dp[0][j] = 0`.
3.  Iterate through the first column. If `obstacleGrid[i][0]` is 0, then `dp[i][0] = dp[i-1][0]`; otherwise, `dp[i][0] = 0`.
4.  Iterate through the rest of the grid. If `obstacleGrid[i][j]` is 0, then `dp[i][j] = dp[i-1][j] + dp[i][j-1]`; otherwise, `dp[i][j] = 0`.
5.  Return `dp[m-1][n-1]`.

**Code (Python):**

```python
def uniquePathsWithObstacles(obstacleGrid):
    m = len(obstacleGrid)
    n = len(obstacleGrid[0])

    # If the starting cell has an obstacle, there are no paths.
    if obstacleGrid[0][0] == 1:
        return 0

    # Initialize the DP table
    dp = [[0] * n for _ in range(m)]

    # Base case: Starting cell
    dp[0][0] = 1

    # Fill the first row
    for j in range(1, n):
        if obstacleGrid[0][j] == 0:
            dp[0][j] = dp[0][j - 1]
        else:
            dp[0][j] = 0

    # Fill the first column
    for i in range(1, m):
        if obstacleGrid[i][0] == 0:
            dp[i][0] = dp[i - 1][0]
        else:
            dp[i][0] = 0

    # Fill the rest of 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]
            else:
                dp[i][j] = 0

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

Code (Java):

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        // If the starting cell has an obstacle, there are no paths.
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }

        // Initialize the DP table
        int[][] dp = new int[m][n];

        // Base case: Starting cell
        dp[0][0] = 1;

        // Fill the first row
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[0][j] == 0) {
                dp[0][j] = dp[0][j - 1];
            } else {
                dp[0][j] = 0;
            }
        }

        // Fill the first column
        for (int i = 1; i < m; i++) {
            if (obstacleGrid[i][0] == 0) {
                dp[i][0] = dp[i - 1][0];
            } else {
                dp[i][0] = 0;
            }
        }

        // Fill the rest of the DP table
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                } else {
                    dp[i][j] = 0;
                }
            }
        }

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

Big O Runtime Analysis

The algorithm iterates through each cell in the obstacleGrid once to fill the dp table. Therefore, the time complexity is O(m * n), where m is the number of rows and n is the number of columns in the grid.

Big O Space Usage Analysis

The algorithm uses a 2D array dp of the same size as the input grid to store the number of unique paths to each cell. Thus, the space complexity is O(m * n).

Edge Cases

1. Starting Cell is an Obstacle: If obstacleGrid[0][0] is 1, there is no path, so return 0.
2. No Obstacles: If there are no obstacles, the result would be the same as the classic "Unique Paths" problem (without obstacles).
3. Obstacle Blocks the Entire Path: If there is an obstacle in every possible path, the result will be 0.
4. m or n is 1: Need to handle the base cases carefully for the first row and first column.