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];
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment