Java O(nm) time, O(1) space


  • -2
    R

    I count the number of possible moves in each space with negative numbers, so I don't have to worry about the positive 1.

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
        for(int i = 0; i < obstacleGrid.length; i++) {
            if(obstacleGrid[i][0] == 1) break;
            obstacleGrid[i][0] = -1;
        }
        
        for(int i = 0; i < obstacleGrid[0].length; i++) {
            if(obstacleGrid[0][i] == 1) break;
            obstacleGrid[0][i] = -1;
        }
        
        for(int i = 1; i < obstacleGrid.length; i++) {
            for(int j = 1; j < obstacleGrid[0].length; j++) {
                if(obstacleGrid[i][j] == 1) continue;
                
                int top = (obstacleGrid[i -1][j] == 1) ? 0 : obstacleGrid[i - 1][j];
                int left = (obstacleGrid[i][j - 1] == 1) ? 0 : obstacleGrid[i][j - 1];
                
                obstacleGrid[i][j] += (top + left);
            }
        }
        int fin = obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
        return (fin <= 0) ? -1*fin : 0;
    }

  • 0
    F

    You actually use the O(nm) space. You can not exclude them just because they are not allocated in your procedure.


Log in to reply
 

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