Unique Paths II Problem Solution

Unique Paths II Problem: 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 * 109.

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

Unique Paths II Problem Solution

Problem Solution In Python

class Solution:
    def uniquePathsWithObstacles(self, og: List[List[int]]) -> int:
        if og[0][0]==1:
            return 0
        else:
            og[0][0]=1
        for i in range(1,len(og)):
            if og[i][0]!=1:
                og[i][0]=og[i-1][0]
            else:
                og[i][0]=0
        for i in range(1,len(og[0])):
            if og[0][i]!=1:
                og[0][i]=og[0][i-1]
            else:
                og[0][i]=0
        for i in range(1,len(og)):
            for j in range(1,len(og[0])):
                if og[i][j]!=1:
                    og[i][j]=og[i-1][j]+og[i][j-1]
                else:
                    og[i][j]=0
        return og[-1][-1]

Problem Solution In Java

public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;
    int[][] s = new int[m][n];
    s[0][0] = obstacleGrid[0][0]==0 ? 1:0;
    if(s[0][0] == 0) return 0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(obstacleGrid[i][j] == 1) s[i][j] = 0;
            else if(i==0){
                if(j>0) s[i][j] = s[i][j-1];
            }
            else if(j==0){
                if(i>0) s[i][j] = s[i-1][j];
            }
            else s[i][j] = s[i-1][j] + s[i][j-1];
        }
    }
    return s[m-1][n-1];
}
}

Problem Solution In C++

class Solution {
public:    
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        
        for(int i = 0; i < obstacleGrid.size(); i++) {
            for (int j = 0; j < obstacleGrid[i].size(); j++) {
                if (obstacleGrid[i][j] == 1) {
                    obstacleGrid[i][j] = 0;
                } else if (i == 0 && j == 0) {
                    obstacleGrid[i][j] = 1;
                } else if (i == 0) {
                    obstacleGrid[i][j] = obstacleGrid[i][j-1];  
                } else if (j == 0) {
                    obstacleGrid[i][j] = obstacleGrid[i-1][j];
                } else {
                    long long int temp = (long long int)obstacleGrid[i-1][j] + (long long int)obstacleGrid[i][j-1];
                    if (temp > INT_MAX) {
                        obstacleGrid[i][j] = -1;
                    } else {
                        obstacleGrid[i][j] = temp;
                    }
                }
            }
        }
    return obstacleGrid[obstacleGrid.size()-1][obstacleGrid[0].size()-1];
    }
};

Problem Solution In C

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridRowSize, int obstacleGridColSize) {

int i, j;
int dp[101][101];
memset(dp, 0, sizeof(dp));

for(i = 1; i <= obstacleGridRowSize; i++){
    for(j = 1; j <= obstacleGridColSize; j++){
        if(obstacleGrid[i - 1][j - 1] != 1 && i == 1 && j == 1){
            dp[i][j] = 1;
            
        }else if(obstacleGrid[i - 1][j - 1] != 1){
            dp[i][j] = dp[i - 1][j] +  dp[i][j - 1];
        }
    }
}
return dp[obstacleGridRowSize][obstacleGridColSize];
}