# 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[0][0]*). 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[0].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[0][0] == 1
- return 0
// set the number of ways to reach the top-left cell as 1
- obstacleGrid[0][0] = 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] == 0
- obstacleGrid[i][0] += obstacleGrid[i - 1][0]
- else
- obstacleGrid[i][0] = 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[0][j] == 0
- obstacleGrid[0][j] += obstacleGrid[0][j - 1]
- else
- obstacleGrid[0][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[0].size();
if(obstacleGrid[0][0] == 1) {
return 0;
}
obstacleGrid[0][0] = 1;
for(int i = 1; i < m; i++) {
if(obstacleGrid[i][0] == 0) {
obstacleGrid[i][0] += obstacleGrid[i - 1][0];
} else {
obstacleGrid[i][0] = 0;
}
}
for(int j = 1; j < n; j++) {
if(obstacleGrid[0][j] == 0) {
obstacleGrid[0][j] += obstacleGrid[0][j - 1];
} else {
obstacleGrid[0][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[0])
if obstacleGrid[0][0] == 1 {
return 0
}
obstacleGrid[0][0] = 1
for i := 1; i < m; i++ {
if obstacleGrid[i][0] == 0 {
obstacleGrid[i][0] += obstacleGrid[i - 1][0]
} else {
obstacleGrid[i][0] = 0
}
}
for j := 1; j < n; j++ {
if obstacleGrid[0][j] == 0 {
obstacleGrid[0][j] += obstacleGrid[0][j - 1]
} else {
obstacleGrid[0][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[0].length;
if(obstacleGrid[0][0] == 1) {
return 0;
}
obstacleGrid[0][0] = 1;
for(let i = 1; i < m; i++) {
if(obstacleGrid[i][0] == 0) {
obstacleGrid[i][0] += obstacleGrid[i - 1][0];
} else {
obstacleGrid[i][0] = 0;
}
}
for(let j = 1; j < n; j++) {
if(obstacleGrid[0][j] == 0) {
obstacleGrid[0][j] += obstacleGrid[0][j - 1];
} else {
obstacleGrid[0][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];
};
```

#### Dry Run

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[0].size()
= 3
Step 2: if obstacleGrid[0][0] == 1
0 == 1
false
Step 3: obstacleGrid[0][0] = 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] == 0
obstacleGrid[1][0] == 0
true
obstacleGrid[i][0] += obstacleGrid[i - 1][0]
= obstacleGrid[i][0] + obstacleGrid[i - 1][0]
= obstacleGrid[1][0] + obstacleGrid[0][0]
= 0 + 1
= 1
i++
i = 2
for i < m
2 < 3
true
if obstacleGrid[i][0] == 0
obstacleGrid[2][0] == 0
true
obstacleGrid[i][0] += obstacleGrid[i - 1][0]
= obstacleGrid[i][0] + obstacleGrid[i - 1][0]
= obstacleGrid[2][0] + obstacleGrid[1][0]
= 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[0][j] == 0
obstacleGrid[0][1] == 0
true
obstacleGrid[0][j] += obstacleGrid[0][j - 1]
= obstacleGrid[0][j] + obstacleGrid[0][j - 1]
= obstacleGrid[0][1] + obstacleGrid[0][0]
= 0 + 1
= 1
j++
j = 2
for j < n
2 < 3
true
if obstacleGrid[0][j] == 0
obstacleGrid[0][2] == 0
true
obstacleGrid[0][j] += obstacleGrid[0][j - 1]
= obstacleGrid[0][j] + obstacleGrid[0][j - 1]
= obstacleGrid[0][2] + obstacleGrid[0][1]
= 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[1][1] == 0
1 == 0
false
else
obstacleGrid[i][j] = 0
obstacleGrid[1][1] = 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[1][2] == 0
true
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
= obstacleGrid[1 - 1][2] + obstacleGrid[1][2 - 1]
= obstacleGrid[0][2] + obstacleGrid[1][1]
= 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[2][1] == 0
true
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
= obstacleGrid[2 - 1][1] + obstacleGrid[2][1 - 1]
= obstacleGrid[1][1] + obstacleGrid[2][0]
= 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[2][2] == 0
true
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
= obstacleGrid[2 - 1][2] + obstacleGrid[2][2 - 1]
= obstacleGrid[1][2] + obstacleGrid[2][1]
= 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][2]
2
We return the answer as 2.
```