Easy java solution in 1 ms


  • 0
    D

    public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        //Base case: if number of rows or columns is 0 or starting point is 0
        if(obstacleGrid.length==0 || obstacleGrid[0].length==0 || obstacleGrid[0][0]==1)
            return 0;
        
        //length of rows and columns in the matrix   
        int rows=obstacleGrid.length;
        int columns=obstacleGrid[0].length;
        
        //variables to see if unique paths exist in first row and column
        int rest_rows=0;
        int rest_cols=0;
        
        
        for(int i=0;i<rows;i++)
        {
            //if entry is 0 path exists, else everything after that is unreachable
            if(obstacleGrid[i][0]==0 && rest_rows==0)
                obstacleGrid[i][0]=1;
            else
            {
                obstacleGrid[i][0]=0;
                rest_rows=1;
            }
        }
        
        
        for(int i=1;i<columns;i++)
        {
            //if entry is 0 path exists, else everything after that is unreachable
            if(obstacleGrid[0][i]==0 && rest_cols==0)
                obstacleGrid[0][i]=1;
            else
            {
                obstacleGrid[0][i]=0;
                rest_cols=1;
            }
        }
        
        for(int i=1;i<rows;i++)
        {
            for(int j=1;j<columns;j++)
            {
                //if it is an obstacle, no path exists to it, else update the path
                if(obstacleGrid[i][j]==1)
                    obstacleGrid[i][j]=0;
                else
                    obstacleGrid[i][j]=obstacleGrid[i-1][j]+obstacleGrid[i][j-1];
            }
        }
        
        return obstacleGrid[rows-1][columns-1];
        
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.