# Unique Paths II

​A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as `1` and `0` respectively in the grid.

Note: m and n will be at most 100.

Example 1:

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

This is an extension of Find Unique Paths I. The robot can only move either down or right. Hence any cell in the first row can only be reached from the cell left to it. And, any cell in the first column can only be reached from the cell above it.

#### ALGORITHM:

1. If the first cell `obstacleGrid[0,0]` contains `1`, this means there is an obstacle in the first cell. Hence the robot won’t be able to make any move.
2. Iterate the first `Row`. Set a value `1` to all the cells unless you get an obstacle. If we get an obstacle then set a value `0` to this cell along with all subsequent cells.
3. Iterate the first `Column`. Set a value `1` to all the cells unless you get an obstacle. If we get an obstacle then set a value `0` to this cell along with all subsequent cells.
4. We can use a boolean flag to track, if an obstacle is found or not during iteration.
5. Now, iterate through the array starting from cell `obstacleGrid[1,1]`. If a cell originally doesn’t contain any obstacle then the number of ways of reaching that cell would be the sum of the number of ways of reaching the cell above it and number of ways of reaching the cell to the left of it.
1. `obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]`
6. If a cell contains an obstacle set it to `0` and continue. This is done to make sure it doesn’t contribute to any other path.
```class UniquePathIISolution {

public int uniquePathsWithObstacles(int[][] obstacleGrid) {

// If the starting cell has an obstacle, then simply return
// as there would be no paths to the destination.
if (obstacleGrid[0][0] == 1) {
return 0;
}
int rows = obstacleGrid.length;
int columns = obstacleGrid[0].length;

// Filling the values for the first column
boolean obstacleFound = false;
for (int i = 0; i < rows; i++) {
if (obstacleGrid[i][0] == 0 && !obstacleFound) {
obstacleGrid[i][0] = 1;
} else {
obstacleGrid[i][0] = 0;
obstacleFound = true;
}
}

// Filling the values for the first row
obstacleFound = false;
for (int i = 1; i < columns; i++) {
if (obstacleGrid[0][i] == 0 && !obstacleFound) {
obstacleGrid[0][i] = 1;
} else {
obstacleGrid[0][i] = 0;
obstacleFound = true;
}
}

// Starting from cell(1,1) fill up the values
// No. of ways of reaching cell[i][j] = cell[i - 1][j] + cell[i][j - 1]
// i.e. From above and left.
for (int i = 1; i < rows; i++) {
for (int j = 1; j < columns; j++) {
if (obstacleGrid[i][j] == 0) {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
} else {
obstacleGrid[i][j] = 0;
}
}
}
// Return value stored in rightmost bottommost cell. That is the destination.
return obstacleGrid[rows - 1][columns - 1];
}
}

public class UniquePathII {
public static void main(String[] args) {
int[][] obstacleGrid = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
UniquePathIISolution solution = new UniquePathIISolution();
System.out.println("No of paths :" + solution.uniquePathsWithObstacles(obstacleGrid));
}
}
```

Complexity Analysis

• Time Complexity: O(M×N). The rectangular grid given to us is of size M×N and we process each cell just once.
• Space Complexity: O(1). We are utilizing the `obstacleGrid` as the DP array. Hence, no extra space.