Leetcode 63. Unique Paths II

Problem Link: https://leetcode.com/problems/unique-paths-ii/

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 is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:
Input:
[
  [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:

Suppose we are at any cell (i, j). Then, the number of ways to reach the cell (i, j) is the sum of number of ways to reach cell (i - 1, j) (above) and (i, j - 1) (left) i.e

          numways(i, j) = numways(i - 1, j) + numways(i, j - 1) 

Instead of using the recursive approach I'm gonna use bottom-up dp to solve the problem.
Let's say dp[i][j] gives the number of ways to reach cell (i, j).
Then,

          dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

The added constraints in the problem is that any cell(i, j) can be either 1 or 0 where 1 denotes there is an obstacle. Clearly

  if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                }
                else{
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
             }

This is because if the cell(i, j) has obstacle then there is no way we can reach cell (i, j)

We have to handle the base case when the cell is of size 1 * 1. If the cell at (0, 0) has obstacle then there is no way we can reach cell(0, 0) . So we immediately return 0. Else we return 1 as there is only 1 way in tbis case

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

Let's see the first row and first column.

What is the number of ways to reach any cell (i, 0) or (0, j) ???

There is only one way to reach cell (i, 0) i.e only from upward direction i.e cell (i - 1, 0).

So,

          dp[i][0] = dp[i - 1][j]

Similarly, there is only one way to reach cell (0, j) i.e only from left direction i.e cell (0, j - 1).

So,

          dp[0][j] = dp[0][j - 1]

Using the added constraints in the problem we can rewrite these two conditions as:
We can write the code for first column as

if(obstacleGrid[i][0] == 1){
                dp[i][0] = 0;
}
else if(i < 1){
                dp[i][0] = 1;
}
else{
                dp[i][0] = dp[i - 1][0];
}

Similarly for first row:

if(obstacleGrid[i][0] == 1){
                dp[i][0] = 0;
}
else if(i < 1){
                dp[i][0] = 1;
}
else{
                dp[i][0] = dp[i - 1][0];
}

Implementation:

 class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
     
     
     // FInd number of rows
        int m = obstacleGrid.size();
        
        // Find number of columns 
        int n = obstacleGrid[0].size();
        
        // dp[i][j] gives the num of ways to reach cell(i, j)
        // Initialise 2d array of size m * n with 0
        vector<vector<long long>> dp(m, vector<long long> (n, 0));
        
        // Base condition: If there is only 1 cell
        if(m == 1 && n == 1){
             if(obstacleGrid[0][0] == 1){
                 return 0;
            }
            return 1;
        }
        
        
        
  
        // First column cell (i, 0) can be reached from cell (i - 1, 0)
        for(int i = 0; i < m; i++){
         // If any cell (i, 0) contains obstacle then there is no way to reach the cell(i, j)
         // so dp[i][0] = 0
            if(obstacleGrid[i][0] == 1){
                dp[i][0] = 0;
            }
            // else if it is the first cell (0, 0) and there is no obstacle then
         // dp[i][0] = 1
            else if(i < 1){
                 dp[i][0] = 1;
            }
            // Otherwise we can reach cell (i, 0) from cell(i - 1, 0)
      // so dp[i][0] = dp[i - 1][0]
            else{
                 dp[i][0] = dp[i - 1][0];
            }
           
        }
        
        // First row cell (0, i) can be reached from cell (0, i - 1)
         for(int i = 0; i < n; i++){
          // If any cell (0, i) contains obstacle then there is no way to reach the cell(0, i)
         // so dp[0][i] = 0
            if(obstacleGrid[0][i] == 1){
                dp[0][i] = 0;
            }
            // else if it is the first cell (0, 0) and there is no obstacle then
         // dp[0][i] = 1
            else if(i < 1){
                 dp[0][i] = 1;
            }
            // Otherwise we can reach cell (0, j) from cell(0, j - 1)
         // so dp[0][i] = dp[0][i - 1]
            else{
                    dp[0][i] = dp[0][i - 1];
            }
        }
        
        
        // For every other cells (1, 1) to (m - 1, n - 1)
        // Build dp table in bottom up manner
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
             // If obstacle no way to reach cell(i, j)
             // So dp[i][j] =0 
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                }
                //Else num of ways to reach cell(i, j) is
                // the sum of num of ways to reach cell(i - 1, j) and (i, j - 1)
                else{
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
            }
         
        }

  // return num of ways to reach cell(m - 1, n - 1)      
        return dp[m - 1][n - 1];
    }
};

Here is a slightly simpler version of this problem: https://leetcode.com/problems/unique-paths/