 # LeetCode - Unique Path II

### Problem statement

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10^9.

Problem statement taken from: https://leetcode.com/problems/unique-paths-ii

Example 1: ``````Input: obstacleGrid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3 x 3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right``````

Example 2: ``````Input: obstacleGrid = [[0, 1], [0, 0]]
Output: 1``````

Constraints:

``````- m == obstacleGrid.length
- n == obstacleGrid[i].length
- 1 <= m, n <= 100
- obstacleGrid[i][j] is 0 or 1``````

### Explanation

The problem is similar to our previous blog post Unique Paths. It can be solved using Brute force or a Dynamic Programming approach.

But the only case we need to handle is obstacles in the path. If an obstacle is present in a cell [i, j], there is no way we can reach the following cells:

• [i, j + 1] // right cell
• [i + 1, j] // bottom cell

We can just mark the [i, j] cell path count as 0. Which indicates there is no possible way to reach this cell.

#### Dynamic Programming

Based on the above approach, let's jump to the algorithm directly.

``````- set m = obstacleGrid.size()
n = obstacleGrid.size()

// if the top-left cell has an obstacle, the robot cannot be placed and
// start moving across the grid. We return 0 in such a case.
- if obstacleGrid == 1
- return 0

// set the number of ways to reach the top-left cell as 1
- obstacleGrid = 1

// following loop sets the number of ways to reach any cell in the left-most column.
// if we have an obstacle, mark the number of ways to reach that cell
// and all its bottom-adjacent cells as 0.
- loop for i = 1; i < m; i++
- if obstacleGrid[i] == 0
- obstacleGrid[i] += obstacleGrid[i - 1]
- else
- obstacleGrid[i] = 0
- for end

// following loop sets the number of ways to reach any cell in the top-most row.
// if we have an obstacle, mark the number of ways to reach that cell
// and all its right-adjacent cells as 0.
- loop for j = 1; j < n; j++
- if obstacleGrid[j] == 0
- obstacleGrid[j] += obstacleGrid[j - 1]
- else
- obstacleGrid[j] = 0
- for end

// add the number of ways to reach any cell in the rest of the matrix
- loop for i = 1; i < m; i++
- loop for j = 1; j < n; j++
- if obstacleGrid[i][j] == 0
- obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
- else
- obstacleGrid[i][j] = 0
- if end
- inner for end
- for end

- return obstacleGrid[m - 1][n - 1]``````

The time complexity of this approach is O(M * N), and the space complexity is O(1).

Let's check our algorithm in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid.size();

if(obstacleGrid == 1) {
return 0;
}

obstacleGrid = 1;

for(int i = 1; i < m; i++) {
if(obstacleGrid[i] == 0) {
obstacleGrid[i] += obstacleGrid[i - 1];
} else {
obstacleGrid[i] = 0;
}
}

for(int j = 1; j < n; j++) {
if(obstacleGrid[j] == 0) {
obstacleGrid[j] += obstacleGrid[j - 1];
} else {
obstacleGrid[j] = 0;
}
}

for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(obstacleGrid[i][j] == 0) {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
} else {
obstacleGrid[i][j] = 0;
}
}
}

return obstacleGrid[m - 1][n - 1];
}
};``````

#### Golang solution

``````func uniquePathsWithObstacles(obstacleGrid [][]int) int {
m, n := len(obstacleGrid), len(obstacleGrid)

if obstacleGrid == 1 {
return 0
}

obstacleGrid = 1

for i := 1; i < m; i++ {
if obstacleGrid[i] == 0 {
obstacleGrid[i] += obstacleGrid[i - 1]
} else {
obstacleGrid[i] = 0
}
}

for j := 1; j < n; j++ {
if obstacleGrid[j] == 0 {
obstacleGrid[j] += obstacleGrid[j - 1]
} else {
obstacleGrid[j] = 0
}
}

for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if obstacleGrid[i][j] == 0 {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
} else {
obstacleGrid[i][j] = 0
}
}
}

return obstacleGrid[m - 1][n - 1]
}``````

#### Javascript solution

``````var uniquePathsWithObstacles = function(obstacleGrid) {
let m = obstacleGrid.length;
let n = obstacleGrid.length;

if(obstacleGrid == 1) {
return 0;
}

obstacleGrid = 1;

for(let i = 1; i < m; i++) {
if(obstacleGrid[i] == 0) {
obstacleGrid[i] += obstacleGrid[i - 1];
} else {
obstacleGrid[i] = 0;
}
}

for(let j = 1; j < n; j++) {
if(obstacleGrid[j] == 0) {
obstacleGrid[j] += obstacleGrid[j - 1];
} else {
obstacleGrid[j] = 0;
}
}

for(let i = 1; i < m; i++) {
for(let j = 1; j < n; j++) {
if(obstacleGrid[i][j] == 0) {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
} else {
obstacleGrid[i][j] = 0;
}
}
}

return obstacleGrid[m - 1][n - 1];
};``````

Let's dry-run our algorithm for Example 1.

``````Input: obstacleGrid = [
[0, 0, 0],
[0, 1, 0],
[0, 0, 0]
]

Step 1: m = obstacleGrid.size()
= 3
n = obstacleGrid.size()
= 3

Step 2: if obstacleGrid == 1
0 == 1
false

Step 3: obstacleGrid = 1
obstacleGrid = [
[1, 0, 0],
[0, 1, 0],
[0, 0, 0]
]

Step 4: loop for i = 1; i < m;
1 < 3
true

if obstacleGrid[i] == 0
obstacleGrid == 0
true

obstacleGrid[i] += obstacleGrid[i - 1]
= obstacleGrid[i] +  obstacleGrid[i - 1]
= obstacleGrid + obstacleGrid
= 0 + 1
= 1

i++
i = 2

for i < m
2 < 3
true

if obstacleGrid[i] == 0
obstacleGrid == 0
true

obstacleGrid[i] += obstacleGrid[i - 1]
= obstacleGrid[i] +  obstacleGrid[i - 1]
= obstacleGrid + obstacleGrid
= 0 + 1
= 1

i++
i = 3

for i < m
3 < 3
false

obstacleGrid = [
[1, 0, 0],
[1, 1, 0],
[1, 0, 0]
]

Step 5: loop for j = 1; j < n;
1 < 3
true

if obstacleGrid[j] == 0
obstacleGrid == 0
true

obstacleGrid[j] += obstacleGrid[j - 1]
= obstacleGrid[j] + obstacleGrid[j - 1]
= obstacleGrid + obstacleGrid
= 0 + 1
= 1

j++
j = 2

for j < n
2 < 3
true

if obstacleGrid[j] == 0
obstacleGrid == 0
true

obstacleGrid[j] += obstacleGrid[j - 1]
= obstacleGrid[j] + obstacleGrid[j - 1]
= obstacleGrid + obstacleGrid
= 0 + 1
= 1

j++
j = 3

for j < n
3 < 3
false

obstacleGrid = [
[1, 1, 1],
[1, 1, 0],
[1, 0, 0]
]

Step 6: loop for i = 1; i < m; i++
loop for j = 1; j < n; j++

if obstacleGrid[i][j] == 0
obstacleGrid == 0
1 == 0
false

else
obstacleGrid[i][j] = 0
obstacleGrid = 0

obstacleGrid = [
[1, 1, 1],
[1, 0, 0],
[1, 0, 0]
]

j++
j = 2

for j < n
2 < 3
true

if obstacleGrid[i][j] == 0
obstacleGrid == 0
true

obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
= obstacleGrid[1 - 1] + obstacleGrid[2 - 1]
= obstacleGrid + obstacleGrid
= 1 + 0
= 1

obstacleGrid = [
[1, 1, 1],
[1, 0, 1],
[1, 0, 0]
]

j++
j = 3

for j < n
3 < 3
false

i++
i = 2

Step 7: loop for i < m
2 < 3
true

loop for j = 1; j < n; j++

if obstacleGrid[i][j] == 0
obstacleGrid == 0
true

obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
= obstacleGrid[2 - 1] + obstacleGrid[1 - 1]
= obstacleGrid + obstacleGrid
= 0 + 1
= 1

obstacleGrid = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 0]
]

j++
j = 2

for j < n
2 < 3
true

if obstacleGrid[i][j] == 0
obstacleGrid == 0
true

obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
= obstacleGrid[2 - 1] + obstacleGrid[2 - 1]
= obstacleGrid + obstacleGrid
= 1 + 1
= 2

obstacleGrid = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 2]
]

j++
j = 3

for j < n
3 < 3
false

i++
i = 3

Step 8: loop for i < m
3 < 3
false

Step 9: return obstacleGrid[m - 1][n - 1]
obstacleGrid[3 - 1][3 - 1]
obstacleGrid
2

We return the answer as 2.``````