This content originally appeared on DEV Community and was authored by seanpgallivan
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:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
A robot is located at the top-left corner of a
m x ngrid (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
1and0respectively 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.
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:
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j]is0or1.
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:
Python can opt to use @lru_cache instead of a standard DP matrix; the standard approach is shown below.
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:
(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:
(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:
(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];
}
};
This content originally appeared on DEV Community and was authored by seanpgallivan
seanpgallivan | Sciencx (2021-04-28T08:31:23+00:00) Solution: Unique Paths II. Retrieved from https://www.scien.cx/2021/04/28/solution-unique-paths-ii/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.