
Description
You are given a m x n
grid filled with non-negative numbers, where some cells may contain obstacles (represented by 1
s). Find the number of unique paths from the top-left corner to the bottom-right corner of the grid. You can only move either down or right at any point in time. A path cannot pass through a cell with an obstacle.
Intuition
The problem can be visualized as navigating a grid where some cells are blocked. To find the number of unique paths to each cell, we need to consider whether the cell is reachable from its possible predecessors (top or left). This suggests a dynamic programming approach where we build up the solution from the smallest subproblems.
Approach
- Initialization:
- Define a 2D list
memo
to store the number of unique paths to each cell, initialized to-1
. - Start from the top-left corner of the grid and recursively compute the number of unique paths to each cell. - Recursive Function:
- Base Cases:
- If the cell indices are out of bounds or the cell contains an obstacle, return
0
. - If the cell is the bottom-right corner, return1
as it represents a valid path. - Memoization: - If the number of unique paths for a cell is already computed (i.e.,memo[i][j] != -1
), return the stored value. - Recursive Calculation: - Compute the number of unique paths for the cell directly below and to the right. - Update the cell's value inmemo
with the sum of the unique paths from the top and left cells. - Result: - The result for the top-left corner of the grid will be the number of unique paths from the top-left to bottom-right.
Complexity
Time Complexity:
O(m * n), where m
is the number of rows and n
is the number of columns in the grid. Each cell is computed only once and stored.
Space Complexity:
O(m * n) for the memoization table memo
, plus the recursion stack space which can be up to O(m + n) in the worst case.
Code
C++
class Solution {
public:
int uniquePathsWithObstacles(vector>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector> memo(m, vector(n, -1));
return dfs(obstacleGrid, 0, 0, memo);
}
private:
int dfs(vector>& obstacleGrid, int i, int j, vector>& memo) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
if (i >= m || j >= n || obstacleGrid[i][j] == 1) return 0;
if (i == m - 1 && j == n - 1) return 1;
if (memo[i][j] != -1) return memo[i][j];
memo[i][j] = dfs(obstacleGrid, i + 1, j, memo) + dfs(obstacleGrid, i, j + 1, memo);
return memo[i][j];
}
};
Python
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
memo = [[-1 for _ in range(n)] for _ in range(m)]
return self.dfs(obstacleGrid, 0, 0, memo)
def dfs(self, obstacleGrid: List[List[int]], i: int, j: int, memo: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
if i >= m or j >= n or obstacleGrid[i][j] == 1:
return 0
if i == m - 1 and j == n - 1:
return 1
if memo[i][j] != -1:
return memo[i][j]
memo[i][j] = self.dfs(obstacleGrid, i + 1, j, memo) + self.dfs(obstacleGrid, i, j + 1, memo)
return memo[i][j]
Java
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] memo = new int[m][n];
// Initialize the memoization array with -1
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
memo[i][j] = -1;
}
}
return dfs(obstacleGrid, 0, 0, memo);
}
private int dfs(int[][] obstacleGrid, int i, int j, int[][] memo) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
if (i >= m || j >= n || obstacleGrid[i][j] == 1) {
return 0;
}
if (i == m - 1 && j == n - 1) {
return 1;
}
if (memo[i][j] != -1) {
return memo[i][j];
}
memo[i][j] = dfs(obstacleGrid, i + 1, j, memo) + dfs(obstacleGrid, i, j + 1, memo);
return memo[i][j];
}
}
JavaScript
var uniquePathsWithObstacles = function (obstacleGrid) {
const m = obstacleGrid.length;
const n = obstacleGrid[0].length;
let memo = Array.from({ length: m }, () => Array(n).fill(-1));
function dfs(i, j) {
if (i >= m || j >= n || obstacleGrid[i][j] === 1) return 0;
if (i === m - 1 && j === n - 1) return 1;
if (memo[i][j] !== -1) return memo[i][j];
memo[i][j] = dfs(i + 1, j) + dfs(i, j + 1);
return memo[i][j];
}
return dfs(0, 0);
};