Java Solution using Dynamic Programming, O(1) space


  • 33
    V
    public class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            
            //Empty case
            if(obstacleGrid.length == 0) return 0;
            
            int rows = obstacleGrid.length;
            int cols = obstacleGrid[0].length;
            
            for(int i = 0; i < rows; i++){
                for(int j = 0; j < cols; 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] * 1;// For row 0, if there are no paths to left cell, then its 0,else 1
                    else if(j == 0)
                        obstacleGrid[i][j] = obstacleGrid[i - 1][j] * 1;// For col 0, if there are no paths to upper cell, then its 0,else 1
                    else
                        obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
                }
            }
            
            return obstacleGrid[rows - 1][cols - 1];
            
        }
    }

  • 0
    R

    That multiplication approach to the DP is really brilliant! Thank you for sharing.


  • 1
    R

    It's beautiful to utilize those 1s and 0s.


  • 0
    N
    This post is deleted!

  • 0
    O

    Can anyone help me understand what does the multiplication by 1 do in the code? I don't see it add any extra functions to the code? Basically, anything multiplied by 1 is still itself. Did I miss something?


  • 0
    H

    Good Solution. It's not that easy to find out all if cases.


  • 3
    H

    This is a very nice solution but the title is a bit misleading - you are using O(1) space in the sense that you are using O(1) extra space. In reality you are overwriting the original matrix, and in doing so you are using O(m * n) space. This may not be allowed in production settings.


  • 0
    G

    yeah, I think so.


  • 0
    S

    I have the same question. at first I thought I was missing something brilliant but eventually I don't see the point of * 1 in this case, other than adding to explaining the rationale nominally?


  • 0
    C

    @james.wang.cccgmail.com
    @optimus

    http://imgur.com/a/hvjCf

    Say for example, you are looking at an element in the first row (row 0), and there's an obstacle in the second column (col 1), because for elements in the first row, the only possible path from (0,0) is to keep going right, (0, 1), (0, 2) ... Any obstacles in the way will block this path for all elements to the right of it.

    Now let's look at how this logic is implemented in code. If there is an obstacle in the first row (i == 0), the first if statement, if(obstacleGrid[i][j] == 1) obstacleGrid[i][j] = 0; will turn this element into 0. Any elements to its right (with larger j values) will be turned into 0 by the third statement obstacleGrid[i][j] = obstacleGrid[i][j - 1] * 1, meaning we cannot get to (i,j) from (0,0). Well of course that's the case, because the only path to (i,j) is blocked by the obstacle in first row.

    Hope that makes sense..


  • 0
    E

    I agree with what @hllowrld said that modifying the original matrix may not be allowed in production settings. After calling this function, the input no longer stores the values of grid, but the sum of paths, which can cause confusion and is dangerous in reality. It is good to try reducing the memory usage, but not in this way.


Log in to reply
 

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