We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Unique Paths II

Number: 63

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Nvidia, Agoda, Meta, Bloomberg, TikTok, Microsoft, Pinterest, tcs, Coupang, Cruise, Atlassian, Yahoo, Apple, Uber, athenahealth

Problem Description

Given an m x n grid where some cells contain obstacles (represented by 1) and others are free (represented by 0), a robot starts at the top-left corner and wants to reach the bottom-right corner by only moving either down or right. The task is to compute the number of unique paths that avoid obstacles.

Key Insights

  • Use Dynamic Programming (DP) to build up the solution by calculating the number of paths to reach each cell.
  • For any cell, if it is not an obstacle, the number of paths to reach it equals the sum of the paths from the cell directly above and the cell to the left.
  • Cells containing obstacles are set to 0, meaning no path can go through them.
  • Special handling is required for the first row and first column since the robot can only come from one direction for those cells.
  • If the starting cell has an obstacle, the answer is immediately 0.

Space and Time Complexity

Time Complexity: O(m * n) - Each cell is processed once.
Space Complexity: O(m * n) - Using an auxiliary grid for DP. An optimization to O(n) space is possible by reusing a single row.

Solution

We use a 2D dynamic programming approach where a dp array is maintained with the same dimensions as the grid. Initially, dp[0][0] is set to 1 if the starting cell is free, otherwise 0. The first row and first column are filled based on the absence of obstacles until a blockage is met. Then, for every other cell, if it is free, the value in dp[i][j] is computed as the sum of dp[i-1][j] (from above) and dp[i][j-1] (from left). If the cell is an obstacle, the value is 0. This continues until the bottom-right cell is computed.

Code Solutions

# Function to calculate unique paths with obstacles in a grid
def uniquePathsWithObstacles(obstacleGrid):
    # If the starting cell has an obstacle return 0 immediately
    if not obstacleGrid or obstacleGrid[0][0] == 1:
        return 0
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    
    # Create a dp grid with same dimensions initialized to 0
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1  # start position
    
    # Fill the first column considering obstacles
    for i in range(1, m):
        dp[i][0] = 0 if obstacleGrid[i][0] == 1 else dp[i-1][0]
    
    # Fill the first row considering obstacles
    for j in range(1, n):
        dp[0][j] = 0 if obstacleGrid[0][j] == 1 else dp[0][j-1]
    
    # Fill the rest dp table
    for i in range(1, m):
        for j in range(1, n):
            if obstacleGrid[i][j] == 1:
                dp[i][j] = 0  # obstacle cell
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]  # paths from top and left
    return dp[m-1][n-1]

# Example usage:
grid = [[0,0,0],[0,1,0],[0,0,0]]
print(uniquePathsWithObstacles(grid))  # Output: 2
← Back to All Questions