Easy Java solution, in-place, DP


  • 13
    Y

    The idea is simple, set all obstacles to be 0 while doing the DP. No extra space is used.

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