*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #63 (*Medium*): Unique Paths II

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

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.

####
*Examples:*

*Examples:*

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 -> RightVisual:

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

####
*Constraints:*

*Constraints:*

`m == obstacleGrid.length`

`n == obstacleGrid[i].length`

`1 <= m, n <= 100`

`obstacleGrid[i][j]`

is`0`

or`1`

.

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

The naive approach here would be to try every path with a **recursive** **depth first search** (**DFS**) approach. That would involve duplicating the processing used for repeating subpaths, however, which would quickly lead to a **TLE** result. When faced with repeating subproblems, we should be thinking of a **dynamic programming** (**DP**) approach to store completed subproblem and avoid any unnecessary duplication of processing.

In this situation, we can create a DP matrix (**dp**) in the same dimensions as our input matrix (**OG**). (* Note: We can choose to use an in-place approach here and use OG as our DP matrix in order to reduce the space complexity of our solution to O(1).*) Each cell in

**dp**will represent the number of paths that lead to the corresponding cell in

**OG**. Since the robot can only move either to the right or down, we can perform a

**bottom-up**DP solution, working from the initial cell and iterating downward and rightward through

**OG**.

Each cell in **OG** (**OG[i][j]**) can potentially reached by only two previously-visited cells (**OG[i-1][j]** & **OG[i][j-1]**), so the number of ways to reach the current cell (**dp[i][j]**) should be the sum of the ways to reach those other two cells (**dp[i-1][j] + dp[i][j-1]**), should they exist.

Since any cell representing an obstacle cannot be a part of a path, its value in **dp** should be **0**. We'll also need to seed the initial starting position with a value of **1** to represent the single initial path. Once we're done building **dp**, the value of the bottom-right cell should be our answer.

**Time Complexity: O(N * M)**where**N**and**M**are the dimensions of the input matrix-
**Space Complexity: O(N * M)**for the DP matrix*or***O(1)**if we use an**in-place**approach for the DP matrix

####
*Implementation:*

*Implementation:*

Python can opt to use **@lru_cache** instead of a standard DP matrix; the standard approach is shown below.

####
*Javascript Code:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
var uniquePathsWithObstacles = function(OG) {
if (OG[0][0]) return 0
let m = OG.length, n = OG[0].length
let dp = Array.from({length: m}, el => new Uint32Array(n))
dp[0][0] = 1
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (OG[i][j] || (!i && !j)) continue
else dp[i][j] = (i ? dp[i-1][j] : 0) + (j ? dp[i][j-1] : 0)
return dp[m-1][n-1]
};
```

####
*Python Code:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution:
def uniquePathsWithObstacles(self, OG: List[List[int]]) -> int:
if OG[0][0]: return 0
m, n = len(OG), len(OG[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = 1
for i in range(m):
for j in range(n):
if OG[i][j] or (i == 0 and j == 0): continue
dp[i][j] = (dp[i-1][j] if i else 0) + (dp[i][j-1] if j else 0)
return dp[m-1][n-1]
```

####
*Java Code:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public int uniquePathsWithObstacles(int[][] OG) {
if (OG[0][0] == 1) return 0;
int m = OG.length, n = OG[0].length;
int[][] dp = new int[m][n];
dp[0][0] = 1;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (OG[i][j] == 1 || (i == 0 && j == 0)) continue;
else dp[i][j] = (i > 0 ? dp[i-1][j] : 0) + (j > 0 ? dp[i][j-1] : 0);
return dp[m-1][n-1];
}
}
```

####
*C++ Code:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& OG) {
if (OG[0][0] == 1) return 0;
int m = OG.size(), n = OG[0].size();
vector<vector<int>> dp(m, vector<int>(n,0));
dp[0][0] = 1;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (OG[i][j] == 1 || (i == 0 && j == 0)) continue;
else dp[i][j] = (i > 0 ? dp[i-1][j] : 0) + (j > 0 ? dp[i][j-1] : 0);
return dp[m-1][n-1];
}
};
```

## Top comments (0)