Bottom up iterative solution, O(mn), no extra space


  • 7
    M
     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        
        for (int r = m - 1; r >= 0; r--) {
            for (int c = n - 1; c >= 0; c--) {
                if (obstacleGrid[r][c] == 1) obstacleGrid[r][c] = 0;
                else {
                    if (r == m - 1 && c == n - 1) obstacleGrid[r][c] = 1;
                    else if (r == m - 1) obstacleGrid[r][c] = obstacleGrid[r][c + 1];
                    else if (c == n - 1) obstacleGrid[r][c] = obstacleGrid[r + 1][c];
                    else obstacleGrid[r][c] = obstacleGrid[r][c + 1] + obstacleGrid[r + 1][c];
                }
            }
        }
        
        return obstacleGrid[0][0];
    }

  • 0
    M

    Just realized that this might not be a good solution, because the original array is corrupted...


  • 0
    S

    Actually, it's a good catch to make use of the original array


  • 0
    S

    Yeah, that's really good solution. In the problem desc. they didn't ask to maintain the original array.


  • 0
    S

    Here's same idea in C++

    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        
        for(int i= m-1;i>=0;--i)
            for(int j=n-1;j>=0;--j)
            {
                if(obstacleGrid[i][j] == 1)
                    obstacleGrid[i][j] = 0;
                else
                {
                    if(i == m-1 && j == n-1)
                        obstacleGrid[i][j] = 1;
                    else if(i == m-1)
                        obstacleGrid[i][j] = obstacleGrid[i][j+1];
                    else if(j == n-1)
                        obstacleGrid[i][j] = obstacleGrid[i+1][j];
                    else
                        obstacleGrid[i][j] = obstacleGrid[i][j+1] + obstacleGrid[i+1][j];
                }
            }
            
        return obstacleGrid[0][0];
    }

  • 0
    C

    please ignore my last comment


Log in to reply
 

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