Java code, Dynamic Programming, linear time (wrt size of matrix), constant space


  • 0

    The idea is to take the sum of the element on the left and element above. We convert the element inside the matrix to the number of distinct paths to get there. If the current element is 1, there can't be any path to here. The 3 lines above the last "else" to handle edge cases.

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length, n=obstacleGrid[0].length;
        for (int i=0; i<m; i++)
            for (int j=0; j<n; 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 obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1];
        return obstacleGrid[m-1][n-1];
    }

Log in to reply
 

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