Leetcode Unique Paths II Problem Solution

In this Leetcode Unique Paths II Problem Solution 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.

Problem solution in Python.

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m=len(obstacleGrid)
        n=len(obstacleGrid[0])
        if obstacleGrid[0][0] == 1:
            return 0
        obstacleGrid[0][0] = 1
 
 
        for j in range(1,n):
            obstacleGrid[0][j]=int(obstacleGrid[0][j]==0 and obstacleGrid[0][j-1]==1)
        for k in range(1,m):
            obstacleGrid[k][0]=int(obstacleGrid[k][0]==0 and obstacleGrid[k-1][0]==1)
 
        for row in range(1,m):
            for column in range(1,n):
                if obstacleGrid[row][column]==0:
                    obstacleGrid[row][column]=obstacleGrid[row-1][column]+obstacleGrid[row][column-1]
                else:
                    obstacleGrid[row][column]=0
        return obstacleGrid[m-1][n-1]

Problem solution in Java.

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

Problem solution in C++.

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        if(obstacleGrid[m-1][n-1] == 1){
            return 0;
        }
        vector<vector<int>> A(m , vector<int> (n , 1));
        bool flag = true;
        
        for(int i=0;i<m;i++){
            if(obstacleGrid[i][0] == 1){
                flag = false;
            }
            if(flag){
                A[i][0] = 1;
            }else{
                A[i][0] = 0;
            }
        }
        flag = true;
        for(int i=0;i<n;i++){
            if(obstacleGrid[0][i] == 1){
                flag = false;
            }
            if(flag){
                A[0][i] = 1;
            }else{
                A[0][i] = 0;
            }
        }
        
        
        for(int i = 1 ; i < m ; i++){
            for(int j = 1 ; j < n ; j++){
                if(obstacleGrid[i][j] == 1){
                    A[i][j] = 0;
                }else{
                    A[i][j] = A[i - 1][j] + A[i][j - 1];
                }
            }
        }
        
        return A[m-1][n-1];
    }
};

Problem solution in C.

int solve(int **count, int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize, int row, int col) {
    if (row == obstacleGridSize || col == obstacleGridColSize[0] || obstacleGrid[row][col] == 1) {
        return 0;
    }
    
    if (count[row][col] != -1) {
        return count[row][col];
    }
    
    if (row == obstacleGridSize - 1 && col == obstacleGridColSize[0] - 1) {
        count[row][col] = 1;
        return 1;
    }
    
    int down = solve(count, obstacleGrid, obstacleGridSize, obstacleGridColSize, row + 1, col);
    int right = solve(count, obstacleGrid, obstacleGridSize, obstacleGridColSize, row, col + 1);
    int uniquePaths = down + right;
    count[row][col] = uniquePaths;
    return uniquePaths;
}
 
int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){
    int **count = malloc(obstacleGridSize * sizeof(int *));
    for (int i = 0; i < obstacleGridSize; ++i) {
        count[i] = malloc(obstacleGridColSize[0] * sizeof(int));
        memset(count[i], -1, obstacleGridColSize[0] * sizeof(int));
    }
 
    int uniquePaths = solve(count, obstacleGrid, obstacleGridSize, obstacleGridColSize, 0, 0);
 
    for (int i = 0; i < obstacleGridSize; ++i) {
        free(count[i]);
    }
    free(count);
    return uniquePaths;
}