Unique Paths Ii - Leetcode Solution

Problem Statement:

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space are marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

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

Solution:

• Approach: Dynamic programming
• Intuition: We will begin by understanding the simple version of this problem that is Unique Paths and then we will extend this logic to solve Unique Paths II by introducing obstacle constraints.
• First, we will find the number of unique paths to each cell of the grid. This can be done using simple recursion that is if n or m is 1, the number of unique paths to the cell will be 1(because we can't move left from start and up from bottom row).

The idea behind the simple version is as follows:

Number of unique paths to reach cell (i, j) = Number of unique paths to reach the cell (i-1, j) + Number of unique paths to reach cell (i, j-1).

• We can extend this idea to the case of Unique Paths II, where there are obstacle constraints.

If a cell (i, j) has an obstacle, then the number of unique paths to the cell (i, j) will be zero because we can't move through obstacles.

More specifically, in terms of recursion:

• If grid[0][0] == 1, then the number of unique paths will be 0.
• If grid[i][j] == 1, then the number of unique paths to the cell (i, j) will be 0.
• If grid[i][j] == 0, then the number of unique paths to the cell (i, j) will be Number of unique paths to the cell (i-1, j) + Number of unique paths to the cell (i, j-1).

We will maintain a 2D array where dp[i][j] represents the number of unique paths to reach the cell (i, j).

• Algorithm:

1. Create a 2D array dp of size (m+1) x (n+1) and initialize all elements with 0.
2. Set dp[0][1]=1. Because the robot can only move down and right, it can't move left. This means that the cell (0, 0) can only be reached by moving down, and the number of unique paths to reach cell (0, 0) will be 1.
3. Loop through every cell of the grid except (0, 0). If grid[i][j] == 1, then the number of unique paths to reach this cell is 0. So, dp[i][j]=0. If grid[i][j] == 0, then the number of unique paths to reach the cell (i, j) will be Number of unique paths to reach the cell (i-1, j) + Number of unique paths to reach the cell (i, j-1). So, dp[i][j]=dp[i-1][j] + dp[i][j-1].
4. Return dp[m-1][n-1]. Because we have initialized the dp array with size (m+1) x (n+1), we will return dp[m-1][n-1] and not dp[m][n].

• Time complexity: O(m*n)
• Space complexity: O(m*n)

Code:

class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size();

    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    //initially we have to start from 0,1 as 0,0 has already been counted
    dp[0][1] = 1;
    
    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            if(obstacleGrid[i-1][j-1] == 1){
                dp[i][j] = 0;
            }
            else{
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    
    return dp[m][n];
}

};

1