# LeetCode 63. Unique Paths II

## Description

https://leetcode.com/problems/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 space is marked as `1` and `0` respectively in the grid.

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 3x3 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

Follow up question for Unique Paths. We can still use a two-dimensional array to show the number of unique paths to each square on the grid.

The number of unique paths to each square on the first column would be 1 if the square is not an obstacle. If the square is an obstacle, the square and the remaining squares on the first column would be 0.

The number of unique paths to each square on the first row would be 1 if the square is not an obstacle. If the square is an obstacle, the square and the remaining squares on the first row would be 0.

The number of unique paths to the squares not at the first row or first column would be the sum of the number of unique paths to its previous left square and top square if the square is not an obstacle. If the square is an obstacle, the unique path would be just 0.

## Java Solution

``````class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid.length == 0) {
return 0;
}

int height = obstacleGrid.length;
int width = obstacleGrid.length;

int[][] paths = new int[height][width];

// first column
for (int i = 0; i < height; i++) {
if (obstacleGrid[i] != 1) {
paths[i] = 1;
} else {
break;
}
}

// first row
for (int j = 0; j < width; j++) {
if (obstacleGrid[j] != 1) {
paths[j] = 1;
} else {
break;
}
}

// for spaces not at first row or first column
for (int i = 1; i < height; i++) {
for (int j = 1; j < width; j++) {
if (obstacleGrid[i][j] != 1) {
paths[i][j] = paths[i - 1][j] + paths[i][j - 1];
}
}
}

return paths[height - 1][width - 1];
}
}``````

## Python Solution

``````class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:

m = len(obstacleGrid)
n = len(obstacleGrid)

paths = [[0 for j in range(n)] for i in range(m)]

for i in range(m):
if obstacleGrid[i] != 1:
paths[i] = 1
else:
break

for j in range(n):
if obstacleGrid[j] != 1:
paths[j] = 1
else:
break

print (paths)

for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 1:
paths[i][j] = 0
else:
paths[i][j] = paths[i - 1][j] + paths[i][j - 1]

return paths[m - 1][n - 1]
``````
• Time Complexity: O(MN).
• Space Complexity: O(MN).

## 2 Thoughts to “LeetCode 63. Unique Paths II”

1. luxegift says: