Taro Logo

Unique Paths II

Medium
Meta logo
Meta
Topics:
Dynamic ProgrammingArrays

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

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

Can you solve this problem efficiently, considering space and time complexity? What are the edge cases we should take into account?

Solution


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.