Dare2Solve
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.
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.
Initialization:
memo
to store the number of unique paths to each cell, initialized to -1
.Recursive Function:
0
.1
as it represents a valid path.memo[i][j] != -1
), return the stored value.memo
with the sum of the unique paths from the top and left cells.Result:
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.
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.
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> memo(m, vector<int>(n, -1));
return dfs(obstacleGrid, 0, 0, memo);
}
private:
int dfs(vector<vector<int>>& obstacleGrid, int i, int j, vector<vector<int>>& 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];
}
};
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]
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];
}
}
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);
};