Solution: Unique Paths II
Tags: algorithms, javascript, java, python
Published: 2021-04-28 08:31:23

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/unique-paths-ii/discuss/1180311).*

---

#### [Leetcode Problem #63 (*Medium*): Unique Paths II](https://leetcode.com/problems/unique-paths-ii/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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:***
>
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.<br>There are two ways to reach the bottom-right corner:<br>1. Right -> Right -> Down -> Down<br>2. Down -> Down -> Right -> Right
Visual:|![Example 1 Visual](https://assets.leetcode.com/uploads/2020/11/04/robot1.jpg)
>
Example 2:||
|---:|---|
Input:|obstacleGrid = [[0,1],[0,0]]
Output:|1
Visual:|![Example 2 Visual](https://assets.leetcode.com/uploads/2020/11/04/robot2.jpg)

---

#### ***Constraints:***
>
 - `m == obstacleGrid.length`
 - `n == obstacleGrid[i].length`
 - `1 <= m, n <= 100`
 - `obstacleGrid[i][j]` is `0` or `1`.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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

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

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
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];
    }
};
```