Unique Paths with Obstacles

Problem Description

You are given an m x n integer array grid representing a grid with obstacles. The robot starts at the top-left corner (0, 0) and tries to reach the bottom-right corner (m-1, n-1). The robot can only move down or right. Obstacles are marked as 1, and empty spaces are marked as 0. The task is to find the number of unique paths the robot can take without stepping on any obstacles.

Naive Approach (Recursion)

A simple approach is to use recursion. We can define a recursive function that takes the current position (row, col) as input. If the current position is the destination, we return 1 (found a path). If the current position is out of bounds or is an obstacle, we return 0 (invalid path). Otherwise, we recursively call the function for the 'down' and 'right' moves and sum the results.

Edge Cases:

• If the starting cell has an obstacle, there are no paths. Return 0.
• If the grid is empty, there are no paths.

Big O Complexity:

• Time Complexity: O(2^(m+n)). In the worst case, the recursion tree can have a depth of m+n, and at each step, we have two choices (down or right).
• Space Complexity: O(m+n) due to the recursion depth.

Optimal Approach (Dynamic Programming)

We can optimize the recursive approach using dynamic programming. Instead of recomputing the number of paths for each cell, we can store the results in a table (DP table). The DP table dp[i][j] stores the number of unique paths to reach cell (i, j).

Algorithm:

1. Initialize a DP table of size m x n with 0s.

2. If the starting cell (0, 0) is not an obstacle, set dp[0][0] = 1.

3. Iterate through the grid, and for each cell (i, j):

   • If the cell is an obstacle, set dp[i][j] = 0.
   • Otherwise, dp[i][j] = dp[i-1][j] + dp[i][j-1] (sum of paths from the top and left cells).

   Consider edge cases for the first row and first column to avoid out-of-bounds access.

4. The result is stored in dp[m-1][n-1].

Edge Cases:

• If the starting cell has an obstacle, there are no paths. Return 0.
• If the grid is empty, there are no paths.

Code:

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 DP table
    dp = [[0] * n for _ in range(m)]

    # 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 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]

Big O Complexity:

• Time Complexity: O(m*n). We iterate through each cell in the grid once.
• Space Complexity: O(m*n) to store the DP table.