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];
}
}
Java Solution using Dynamic Programming, O(1) space


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.

@james.wang.cccgmail.com
@optimusSay 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 statementobstacleGrid[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..

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.