Problem 11 - Unique Paths II

This question is an extension to a previous problem which has been solved here. Before diving into this new challenge, make sure to check out the previous problem for a solid foundation.

Explore our archive for previous posts.

Question

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
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.

Approach

This solution is similar to the previous one but considers obstacles in the grid. It checks if the starting cell is an obstacle and returns 0 if it is. It initializes the first row and first column based on the obstacle grid, considering that paths can only be taken if there are no obstacles. Then, it iterates through the remaining cells, calculating the number of unique paths by summing up the paths from the above cell and left cell, but only if the current cell is not an obstacle. Finally, it returns the number of unique paths for the bottom-right cell.

Here are the detailed steps:

1. We initialize the dp array as before, setting dp[0][j] = 1 and dp[i][0] = 1 for valid i and j based on the obstacle grid.

2. When calculating the number of unique paths for each cell dp[i][j], we need to consider the obstacle at that cell. If there is an obstacle at (i, j), we set dp[i][j] = 0 because we cannot reach that cell. Otherwise, we calculate dp[i][j] by summing up the paths from the cell above (dp[i-1][j]) and the cell to the left (dp[i][j-1]) if they are not obstacles.

3. Finally, we return dp[m-1][n-1], which represents the number of unique paths to reach the bottom-right cell while avoiding obstacles.

Solution

Solve it here

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        
        int[][] dp = new int[m][n];
        
        // Check if the starting cell is an obstacle
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        
        // Initialize the first row and first column based on the obstacle grid
        dp[0][0] = 1;
        for (int i = 1; i < m; i++) {
            if (obstacleGrid[i][0] == 0 && dp[i-1][0] == 1) {
                dp[i][0] = 1;
            }
        }
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[0][j] == 0 && dp[0][j-1] == 1) {
                dp[0][j] = 1;
            }
        }
        
        // Calculate the number of unique paths for each cell by summing up the paths from the above cell and left cell
        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];
    }
}

Time and space complexity

Time Complexity: Similar to the previous problem, the time complexity of the above solution is O(M * N), where M and N are the number of rows and columns in the grid. This is because we iterate through each cell in the grid once to calculate the number of unique paths.

Space Complexity: Again, just like the previous solution, the space complexity of the solution is also O(M * N), because we use a 2-D array of size M * N to store the intermediate results.