Well commented simple java solution with O(n) space.


  • 0
    Y
    public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        /*
        Dynamic Programming
        Every point in the grid has two approaches to reach, either from above or from left point. So a way to reach a given point is numofpath[i][j] = numofpath[i][j-1] + numofpath[i-1][j]
        However, consider that there is obstacles in this grid, we should let the numofpath of those points whose value is 1(obstacle) to be 0 since they cannot be passed. 
        At the same time, since we don't need to reconstruct the path, we only need to keep track of the current row we are calculating. And based on the function above, we have to calculat from left to right and replace old values gradually. 
        Then the last one of the array, after the whole loop ends, is what we need. 
        O(m*n) time and O(n) space.
        */
        if (obstacleGrid == null || obstacleGrid.length == 0){
            return 0;
        }
        
        int l = obstacleGrid[0].length; //the number of grids in one row
        int h = obstacleGrid.length; // the number of rows.
        int[] numofpath = new int[l];
        
        //initialize the array. if there is only one row in the grid, then all points on the right side of the obstacle have 0 path to reach.
        //if there is only one point in the grid, we have to consider if it is a obstacle or not. 
        numofpath[0] = obstacleGrid[0][0] == 1? 0 : 1;
        for (int i = 0; i < h; i++){
            // the first column of points can only have paths if this point is not an obstacle and its above rows have paths.
            numofpath[0] = (obstacleGrid[i][0] == 0) && (numofpath[0] != 0)? 1 : 0;
            for (int j = 1; j < l; j++){
                if (obstacleGrid[i][j] == 0){ //there is no obstacle on this grid
                    numofpath[j] += numofpath[j-1];
                }
                if(obstacleGrid[i][j] == 1){ //there is an obstacle on this grid
                    numofpath[j] = 0;
                }
            }
        }
        
        return numofpath[l-1];
        
    }
    

    }


Log in to reply
 

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