Problem Statement:

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.

Solution:

The basic logic that we would like to implement is the following (in pseudocode):

 
fun(i,j)
    if (i,j) is bottom-right corner return 1
    if i,j has obstacle return 0
    return fun(i+1,j) + fun(i,j+1)

Our final answer by this logic is fun(0,0). We can implement this logic in top down or bottom up fashion.

Top down solution:

 
class Solution {
    vector<vector<int>> memo;
public:
    int util(int i, int j, int m, int n, vector<vector<int>>&grid)
    {
        if (i==m-1 && j==n-1) return 1;
        if (i==m || j==n || grid[i][j]) return -1;
        if (memo[i][j]!=-1) return memo[i][j];
        int res = 0;
        int a = util(i+1, j, m, n, grid);
        int b = util(i, j+1, m, n, grid);
        if (a!=-1) res += a;
        if (b!=-1) res += b;
        return memo[i][j] = res;
    }
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) 
    {
        int m=obstacleGrid.size(), n=obstacleGrid[0].size();
        if (obstacleGrid[0][0] || obstacleGrid[m-1][n-1]) return 0;
        memo = vector<vector<int>>(m, vector<int>(n,-1));
        return util(0,0,m,n,obstacleGrid);
    }
};

Bottom-up solution:

 
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) 
    {
        int m=obstacleGrid.size(), n=obstacleGrid[0].size();
        if (obstacleGrid[0][0] || obstacleGrid[m-1][n-1]) return 0;
        vector<vector<int>> res(m, vector<int>(n,0));
        int r=0,c=0;
        while(r<m && obstacleGrid[r][0]==0) {res[r][0]=1; r++;}
        while(c<n && obstacleGrid[0][c]==0) {res[0][c]=1; c++;}
        for(int i=r; i<m; i++) res[i][0]=0;
        for(int j=c; j<n; j++) res[0][j]=0;
        for(int i=1; i<m; i++)
        {
            for(int j=1; j<n; j++)
            {
                if (obstacleGrid[i][j]){res[i][j]=0; continue;}
                res[i][j] = res[i-1][j]+res[i][j-1];
            }
        }
        return res[m-1][n-1];        
    }
};

Bottom-up solution with $O(1)$ memory:

 
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) 
    {
        int m=grid.size(), n=grid[0].size();
        if (grid[0][0] || grid[m-1][n-1]) return 0;
        int r=0,c=1;
        while(r<m && grid[r][0]==0) {grid[r][0]=1; r++;}
        while(c<n && grid[0][c]==0) {grid[0][c]=1; c++;}
        for(int i=r; i<m; i++) grid[i][0]=0;
        for(int j=c; j<n; j++) grid[0][j]=0;
        for(int i=1; i<m; i++)
        {
            for(int j=1; j<n; j++)
            {
                if (grid[i][j]){grid[i][j]=0; continue;}
                grid[i][j] = grid[i-1][j]+grid[i][j-1];
            }
        }
        return grid[m-1][n-1];        
    }
};

TC: $O(mn)$ for all solutions.