Unique Paths II
Avoid going through obstacle and return total number of ways to reach destination
Unique Paths II (With Obstacles)
Problem Statement
You are given an m x n integer grid, grid. A robot starts at the top-left corner (grid[0][0]), and wants to reach the bottom-right corner (grid[m-1][n-1]). The robot can only move down or right at any point.
Obstacles and open spaces are marked as 1 and 0 respectively in the grid. The robot's path cannot pass through any square marked as an obstacle.
Return the number of unique paths the robot can take to reach the bottom-right corner.
Note: The test cases are designed so that the answer will always be less than or equal to
2 × 10⁹.
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 this 3x3 grid. There are two ways to reach the bottom-right corner:
- Right → Right → Down → Down
- Down → Down → Right → Right
Example 2
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
Solution
Brute Force
We use recursion, working backward from the bottom-right corner toward the top-left corner. At each cell, the number of ways to reach it is the sum of the ways to reach the cell above it and the cell to its left.
- If a position is out of bounds, or lands on an obstacle, there are
0ways to reach it from there. - The starting cell
(0, 0)always has exactly1way to "reach" it (since that's where the robot begins).
var uniquePathsWithObstacles = function (obstacleGrid) {
function recurr(i, j) {
if (i < 0 || j < 0 || obstacleGrid[i][j] == 1) {
return 0;
}
if (i == 0 && j == 0) {
return 1;
}
let up = recurr(i - 1, j);
let right = recurr(i, j - 1);
return right + up;
}
let m = obstacleGrid.length;
let n = obstacleGrid[0].length;
return recurr(m - 1, n - 1);
};
Note: The variable named
righthere actually represents the result of moving to(i, j - 1), which is the cell to the left, not the right. This doesn't affect correctness — the final sum is the same either way — but the naming could be a little confusing if you're reading through the logic carefully.
Memoization (Top-Down)
We use the same recursive approach, but store each cell's result in a dp grid the first time we calculate it, so we don't repeat the same calculations.
var uniquePathsWithObstacles = function (obstacleGrid) {
function recurr(i, j, dp) {
if (i < 0 || j < 0 || obstacleGrid[i][j] == 1) {
return 0;
}
if (i == 0 && j == 0) {
return 1;
}
if (dp[i][j] !== 0) {
return dp[i][j];
}
let up = recurr(i - 1, j, dp);
let right = recurr(i, j - 1, dp);
dp[i][j] = right + up;
return dp[i][j];
}
let m = obstacleGrid.length;
let n = obstacleGrid[0].length;
let dp = Array.from({ length: m }, () => Array(n).fill(0));
dp[0][0] = 1;
return recurr(m - 1, n - 1, dp);
};
Note: Since
dpis filled with0by default, this code usesdp[i][j] !== 0to check whether a cell has already been calculated. This works correctly, but it means that any cell whose genuine answer is0paths (for example, a cell that's fully blocked off by obstacles) will never get "cached" — it will simply be recalculated as0again each time it's visited. This doesn't cause incorrect results, but it's a small inefficiency worth knowing about.
Tabulation (Bottom-Up)
Instead of recursing from the end, we build the answer forward, starting from the top-left corner and working toward the bottom-right.
- If a cell has an obstacle, it has
0ways to be reached, and we skip it. - The starting cell has exactly
1way to be reached. - Every other cell's value is the sum of the cell above it and the cell to its left (treating out-of-bounds neighbors as
0).
var uniquePathsWithObstacles = function (obstacleGrid) {
let m = obstacleGrid.length;
let n = obstacleGrid[0].length;
let dp = Array.from({ length: m }, () => Array(n).fill(0));
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
continue;
}
if (i == 0 && j == 0) {
dp[0][0] = 1;
continue;
}
let up = 0;
let left = 0;
if (i > 0) {
up = dp[i - 1][j];
}
if (j > 0) {
left = dp[i][j - 1];
}
dp[i][j] = left + up;
}
}
return dp[m - 1][n - 1];
};