## Description

https://leetcode.com/problems/unique-paths-ii/description/

Follow up for “Unique Paths”:

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.

For example,

There is one obstacle in the middle of a 3×3 grid as illustrated below.

1 2 3 4 5 |
[ [0,0,0], [0,1,0], [0,0,0] ] |

The total number of unique paths is `2`

.

**Note:** *m* and *n* will be at most 100.

## 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.

## Video Tutorial

## Java Solution

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) { return 0; } int height = obstacleGrid.length; int width = obstacleGrid[0].length; int[][] paths = new int[height][width]; // first column for (int i = 0; i < height; i++) { if (obstacleGrid[i][0] != 1) { paths[i][0] = 1; } else { break; } } // first row for (int j = 0; j < width; j++) { if (obstacleGrid[0][j] != 1) { paths[0][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]; } } |