Unique Paths II

MEDIUM

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.

The testcases are generated so that the answer will be less than or equal to 2 * 10⁹.

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

Constraints:

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] is 0 or 1.

Approaches

Checkout 5 different approaches to solve Unique Paths II. Click on different approaches to view the approach and algorithm in detail.

Space-Optimized 1D Dynamic Programming

This approach optimizes the 2D DP solution's space complexity. Since calculating the number of paths for the current row only requires values from the current and previous row, we can use a single 1D array to store the DP values, reducing space from O(m*n) to O(n).

Algorithm

Get grid dimensions m and n.
If obstacleGrid[0][0] == 1, return 0.
Create a 1D DP array dp of size n.
Initialize dp[0] = 1.
Iterate through rows i from 0 to m-1: a. Iterate through columns j from 0 to n-1: i. If obstacleGrid[i][j] == 1, set dp[j] = 0. ii. Else if j > 0, update dp[j] = dp[j] + dp[j-1].
Return dp[n-1].

We use a 1D array dp of size n. dp[j] will represent the number of paths to reach the cell in the current row at column j.

We iterate through the grid row by row. For each row i, we update the dp array. The update rule dp[j] = dp[j] + dp[j-1] works because when we are at (i, j), dp[j] still holds the value from the previous row (i-1, j), and dp[j-1] has just been updated to hold the value for (i, j-1).

Initialization:
- Create a dp array of size n.
- If obstacleGrid[0][0] == 1, return 0. Otherwise, set dp[0] = 1.
Iteration:
- Iterate through rows i from 0 to m-1.
- For each row, iterate through columns j from 0 to n-1.
- If obstacleGrid[i][j] == 1, there are no paths to this cell, so set dp[j] = 0.
- If j > 0, add the paths from the left cell: dp[j] += dp[j-1].
- Note: For the first cell of each row (j=0), if it's an obstacle, dp[0] becomes 0. If not, it retains its value from the previous row, which is correct as it can only be reached from above.

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

        if (obstacleGrid[0][0] == 1) {
            return 0;
        }

        int[] dp = new int[n];
        dp[0] = 1;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                } else if (j > 0) {
                    dp[j] = dp[j] + dp[j - 1];
                }
            }
        }

        return dp[n - 1];
    }
}

Complexity Analysis

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

Pros and Cons

Pros:

Highly efficient in both time and space.
Optimal space complexity among solutions that do not modify the input.

Cons:

The logic can be slightly less intuitive than the 2D DP approach.
The 1D array is overwritten, so we lose the path counts for previous rows.

Code Solutions

Checking out 4 solutions in different languages for Unique Paths II. Click on different languages to view the code.

class Solution {
public
  int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
    int[][] dp = new int[m][n];
    for (int i = 0; i < m && obstacleGrid[i][0] == 0; ++i) {
      dp[i][0] = 1;
    }
    for (int j = 0; j < n && obstacleGrid[0][j] == 0; ++j) {
      dp[0][j] = 1;
    }
    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];
        }
      }
    }
    return dp[m - 1][n - 1];
  }
}

Video Solution

Watch the video walkthrough for Unique Paths II

Patterns:

Dynamic Programming

Data Structures:

ArrayMatrix

Companies:

Adobe |Agoda |Amazon |Apple |