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

• `````` 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];
}``````

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

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

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

• 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];
}``````

• please ignore my last comment

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