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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Unique Paths II

Difficulty: Medium

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.

Key Insights

  • The robot can only move down or right, which simplifies the pathfinding to a directional problem.
  • Obstacles in the grid block potential paths and must be considered in the calculations.
  • Dynamic programming can be used to build the number of unique paths iteratively.
  • The solution involves maintaining a 2D DP array to store the number of ways to reach each cell.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n)

Solution

To solve the problem, we use dynamic programming. We create a 2D array dp where dp[i][j] represents the number of unique paths to reach the cell at (i, j).

  1. Initialize dp[0][0] to 1 if the starting cell is not an obstacle.
  2. Iterate through each cell in the grid:
    • If the cell is an obstacle (grid[i][j] == 1), set dp[i][j] to 0.
    • Otherwise, set dp[i][j] to the sum of the paths from the top cell (dp[i-1][j]) and the left cell (dp[i][j-1]), considering the boundaries of the grid.
  3. The value at dp[m-1][n-1] will give the number of unique paths to the bottom-right corner.

Code Solutions

def uniquePathsWithObstacles(obstacleGrid):
    if not obstacleGrid or obstacleGrid[0][0] == 1:
        return 0

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

    for i in range(m):
        for j in range(n):
            if obstacleGrid[i][j] == 1:
                dp[i][j] = 0
            else:
                if i > 0:
                    dp[i][j] += dp[i-1][j]
                if j > 0:
                    dp[i][j] += dp[i][j-1]

    return dp[m-1][n-1]
← Back to All Questions