# Share my Java solution: O(m*n) time complexity, no extra space.

• Obviously, this is a DP problem.

Let F(i,j) denotes the paths from top left to cell (i,j).

If cell (i,j) has an obstacle, then F(i,j) = 0.
else

for j>0, F(0,j) = F(0,j-1)

for i>0, F(i,0) = F(i-1,0)

for i>0&&j>0, F(i,j) = F(i-1,j)+F(i,j-1)

We can take advantage of the obstacle array without using extra space.

``````    if(obstacleGrid==null||obstacleGrid.length==0)
return 0;

for(int i=0;i<obstacleGrid.length;i++)
for(int j=0;j<obstacleGrid[0].length;j++)
{
if(i==0)
{
if(j==0)
obstacleGrid[0][0] = 1 - obstacleGrid[0][0];
else
obstacleGrid[0][j] = obstacleGrid[0][j]==1?0:obstacleGrid[0][j-1];
}
else
{
if(j==0)
obstacleGrid[i][0] = obstacleGrid[i][0]==1?0:obstacleGrid[i-1][0];
else
obstacleGrid[i][j] = obstacleGrid[i][j]==1?0:(obstacleGrid[i-1][j]+obstacleGrid[i][j-1]);
}
}
return obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1];``````

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