LeetCode - Unique Path II
Problem statement
You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 10^9.
Problem statement taken from: https://leetcode.com/problems/unique-paths-ii
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 3 x 3 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
The problem is similar to our previous blog post Unique Paths. It can be solved using Brute force or a Dynamic Programming approach.
But the only case we need to handle is obstacles in the path. If an obstacle is present in a cell [i, j], there is no way we can reach the following cells:
- [i, j + 1] // right cell
- [i + 1, j] // bottom cell
We can just mark the [i, j] cell path count as 0. Which indicates there is no possible way to reach this cell.
Dynamic Programming
Based on the above approach, let's jump to the algorithm directly.
- set m = obstacleGrid.size()
n = obstacleGrid[0].size()
// if the top-left cell has an obstacle, the robot cannot be placed and
// start moving across the grid. We return 0 in such a case.
- if obstacleGrid[0][0] == 1
- return 0
// set the number of ways to reach the top-left cell as 1
- obstacleGrid[0][0] = 1
// following loop sets the number of ways to reach any cell in the left-most column.
// if we have an obstacle, mark the number of ways to reach that cell
// and all its bottom-adjacent cells as 0.
- loop for i = 1; i < m; i++
- if obstacleGrid[i][0] == 0
- obstacleGrid[i][0] += obstacleGrid[i - 1][0]
- else
- obstacleGrid[i][0] = 0
- for end
// following loop sets the number of ways to reach any cell in the top-most row.
// if we have an obstacle, mark the number of ways to reach that cell
// and all its right-adjacent cells as 0.
- loop for j = 1; j < n; j++
- if obstacleGrid[0][j] == 0
- obstacleGrid[0][j] += obstacleGrid[0][j - 1]
- else
- obstacleGrid[0][j] = 0
- for end
// add the number of ways to reach any cell in the rest of the matrix
- loop for i = 1; i < m; i++
- loop for j = 1; j < n; j++
- if obstacleGrid[i][j] == 0
- obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
- else
- obstacleGrid[i][j] = 0
- if end
- inner for end
- for end
- return obstacleGrid[m - 1][n - 1]
The time complexity of this approach is O(M * N), and the space complexity is O(1).
Let's check our algorithm in C++, Golang, and Javascript.
C++ solution
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
if(obstacleGrid[0][0] == 1) {
return 0;
}
obstacleGrid[0][0] = 1;
for(int i = 1; i < m; i++) {
if(obstacleGrid[i][0] == 0) {
obstacleGrid[i][0] += obstacleGrid[i - 1][0];
} else {
obstacleGrid[i][0] = 0;
}
}
for(int j = 1; j < n; j++) {
if(obstacleGrid[0][j] == 0) {
obstacleGrid[0][j] += obstacleGrid[0][j - 1];
} else {
obstacleGrid[0][j] = 0;
}
}
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(obstacleGrid[i][j] == 0) {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
} else {
obstacleGrid[i][j] = 0;
}
}
}
return obstacleGrid[m - 1][n - 1];
}
};Golang solution
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
m, n := len(obstacleGrid), len(obstacleGrid[0])
if obstacleGrid[0][0] == 1 {
return 0
}
obstacleGrid[0][0] = 1
for i := 1; i < m; i++ {
if obstacleGrid[i][0] == 0 {
obstacleGrid[i][0] += obstacleGrid[i - 1][0]
} else {
obstacleGrid[i][0] = 0
}
}
for j := 1; j < n; j++ {
if obstacleGrid[0][j] == 0 {
obstacleGrid[0][j] += obstacleGrid[0][j - 1]
} else {
obstacleGrid[0][j] = 0
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if obstacleGrid[i][j] == 0 {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
} else {
obstacleGrid[i][j] = 0
}
}
}
return obstacleGrid[m - 1][n - 1]
}Javascript solution
var uniquePathsWithObstacles = function(obstacleGrid) {
let m = obstacleGrid.length;
let n = obstacleGrid[0].length;
if(obstacleGrid[0][0] == 1) {
return 0;
}
obstacleGrid[0][0] = 1;
for(let i = 1; i < m; i++) {
if(obstacleGrid[i][0] == 0) {
obstacleGrid[i][0] += obstacleGrid[i - 1][0];
} else {
obstacleGrid[i][0] = 0;
}
}
for(let j = 1; j < n; j++) {
if(obstacleGrid[0][j] == 0) {
obstacleGrid[0][j] += obstacleGrid[0][j - 1];
} else {
obstacleGrid[0][j] = 0;
}
}
for(let i = 1; i < m; i++) {
for(let j = 1; j < n; j++) {
if(obstacleGrid[i][j] == 0) {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
} else {
obstacleGrid[i][j] = 0;
}
}
}
return obstacleGrid[m - 1][n - 1];
};Dry Run
Let's dry-run our algorithm for Example 1.
Input: obstacleGrid = [
[0, 0, 0],
[0, 1, 0],
[0, 0, 0]
]
Step 1: m = obstacleGrid.size()
= 3
n = obstacleGrid[0].size()
= 3
Step 2: if obstacleGrid[0][0] == 1
0 == 1
false
Step 3: obstacleGrid[0][0] = 1
obstacleGrid = [
[1, 0, 0],
[0, 1, 0],
[0, 0, 0]
]
Step 4: loop for i = 1; i < m;
1 < 3
true
if obstacleGrid[i][0] == 0
obstacleGrid[1][0] == 0
true
obstacleGrid[i][0] += obstacleGrid[i - 1][0]
= obstacleGrid[i][0] + obstacleGrid[i - 1][0]
= obstacleGrid[1][0] + obstacleGrid[0][0]
= 0 + 1
= 1
i++
i = 2
for i < m
2 < 3
true
if obstacleGrid[i][0] == 0
obstacleGrid[2][0] == 0
true
obstacleGrid[i][0] += obstacleGrid[i - 1][0]
= obstacleGrid[i][0] + obstacleGrid[i - 1][0]
= obstacleGrid[2][0] + obstacleGrid[1][0]
= 0 + 1
= 1
i++
i = 3
for i < m
3 < 3
false
obstacleGrid = [
[1, 0, 0],
[1, 1, 0],
[1, 0, 0]
]
Step 5: loop for j = 1; j < n;
1 < 3
true
if obstacleGrid[0][j] == 0
obstacleGrid[0][1] == 0
true
obstacleGrid[0][j] += obstacleGrid[0][j - 1]
= obstacleGrid[0][j] + obstacleGrid[0][j - 1]
= obstacleGrid[0][1] + obstacleGrid[0][0]
= 0 + 1
= 1
j++
j = 2
for j < n
2 < 3
true
if obstacleGrid[0][j] == 0
obstacleGrid[0][2] == 0
true
obstacleGrid[0][j] += obstacleGrid[0][j - 1]
= obstacleGrid[0][j] + obstacleGrid[0][j - 1]
= obstacleGrid[0][2] + obstacleGrid[0][1]
= 0 + 1
= 1
j++
j = 3
for j < n
3 < 3
false
obstacleGrid = [
[1, 1, 1],
[1, 1, 0],
[1, 0, 0]
]
Step 6: loop for i = 1; i < m; i++
loop for j = 1; j < n; j++
if obstacleGrid[i][j] == 0
obstacleGrid[1][1] == 0
1 == 0
false
else
obstacleGrid[i][j] = 0
obstacleGrid[1][1] = 0
obstacleGrid = [
[1, 1, 1],
[1, 0, 0],
[1, 0, 0]
]
j++
j = 2
for j < n
2 < 3
true
if obstacleGrid[i][j] == 0
obstacleGrid[1][2] == 0
true
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
= obstacleGrid[1 - 1][2] + obstacleGrid[1][2 - 1]
= obstacleGrid[0][2] + obstacleGrid[1][1]
= 1 + 0
= 1
obstacleGrid = [
[1, 1, 1],
[1, 0, 1],
[1, 0, 0]
]
j++
j = 3
for j < n
3 < 3
false
i++
i = 2
Step 7: loop for i < m
2 < 3
true
loop for j = 1; j < n; j++
if obstacleGrid[i][j] == 0
obstacleGrid[2][1] == 0
true
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
= obstacleGrid[2 - 1][1] + obstacleGrid[2][1 - 1]
= obstacleGrid[1][1] + obstacleGrid[2][0]
= 0 + 1
= 1
obstacleGrid = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 0]
]
j++
j = 2
for j < n
2 < 3
true
if obstacleGrid[i][j] == 0
obstacleGrid[2][2] == 0
true
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
= obstacleGrid[2 - 1][2] + obstacleGrid[2][2 - 1]
= obstacleGrid[1][2] + obstacleGrid[2][1]
= 1 + 1
= 2
obstacleGrid = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 2]
]
j++
j = 3
for j < n
3 < 3
false
i++
i = 3
Step 8: loop for i < m
3 < 3
false
Step 9: return obstacleGrid[m - 1][n - 1]
obstacleGrid[3 - 1][3 - 1]
obstacleGrid[2][2]
2
We return the answer as 2.