# Simple C++ explained solution with NO extra memory 6 ms

• This problem is a bit tricky as the grid is initialized with 1's for obstructions but 1 can also represent a valid number of paths to a given cell. So the idea is to reuse the original given grid but work with -ve numbers! In the first pass the first row and columns are initialized with -1 and if there are any obstructions we break.

And after that we calculate the rest of the grid by by adding numbers from p[i-1][j] and p[i][j-1]

''''
class Solution {
public:

``````// "og" is obstacle grid
int uniquePathsWithObstacles(vector<vector<int>>& og) {
if (!og.size())
return 0;

int m = og.size();
int n = og[0].size();

// if there is an obstruction at the destination return 0
if (og[m-1][n-1] == 1)
return 0;

// Make first column "-1" and if there is an obstacle at a given cell, all cells after that
// will be 0s as they have already been initialized with 0s and there is no way to get there. Hence
// the total number of paths to reach such cells is 0
for (int i = 0; i < m; i++) {
if (og[i][0] == 1) {
break;
}

og[i][0] = -1;
}

// make first row -1 and if there is an obstacle break so the reaminder
// of the column cells will be 0 as there is no way to get there
for (int j = 0; j < n; j++) {
if (og[0][j] == 1)
break;

og[0][j] = -1;
}

for (int i = 1; i < og.size(); i++) {
for (int j = 1; j < og[i].size(); j++) {
if (og[i][j] == 1)
continue;

int paths = 0;
if (og[i-1][j] != 1) {
paths += og[i-1][j];
}

if (og[i][j-1] != 1) {
paths += og[i][j-1];
}

og[i][j] = paths;
}

}

return -1 * og[m-1][n-1];
}
``````

};
''

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