Unique Grid Paths — Problem Statement & Solution Guide
Problem Description
Given a 2D grid where each cell is marked as either 0 (obstacle) or 1 (safe), find the number of unique paths from the top-left corner to the bottom-right corner. The movement is restricted to only down or right at any point. The grid does not contain obstacles (0s) on the path from top-left to bottom-right.
Examples
Input
[[1,0,0],[0,0,0],[0,0,0]]
Output
0
Explanation: Step-by-step: The grid contains an obstacle (0) on the first row, which blocks the path from top-left to bottom-right. Therefore, there are no unique paths, and the output is 0.
Input
[[1,1,0],[0,0,0],[0,0,1]]
Output
0
Explanation: Step-by-step: The grid contains obstacles (0s) on the path from top-left to bottom-right. Therefore, there are no unique paths, and the output is 0.
Constraints
- The grid size will not exceed 20x20 cells.
- Each cell in the grid will contain either 3 (safe path) or 8 (asteroid field).
- The spacecraft starts at the top left corner and must reach the bottom right corner.
Optimal Approach & Strategy
An optimized approach involves using dynamic programming to store the number of unique paths to each cell, which can be calculated by summing the number of unique paths to the cell above and the cell to the left. This approach has a time complexity of O(m*n), where m and n are the dimensions of the grid.
Brute Force Approach
A brute-force approach would involve recursively trying all possible moves (down and right) from each cell and counting the number of unique paths that reach the bottom right corner. However, this approach has an exponential time complexity due to the overlapping subproblems. It can be improved by using a more efficient algorithm that avoids redundant calculations.
Verified Code Solutions
function uniqueGridPaths(grid) {
if (!grid || grid.length === 0) return 0;
const m = grid.length, n = grid[0].length;
const dp = Array(m).fill().map(() => Array(n).fill(0));
dp[0][0] = grid[0][0] === 1 ? 1 : 0;
for (let i = 1; i < m; i++) {
dp[i][0] = grid[i][0] === 1 ? dp[i-1][0] : 0;
}
for (let j = 1; j < n; j++) {
dp[0][j] = grid[0][j] === 1 ? dp[0][j-1] : 0;
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = grid[i][j] === 1 ? dp[i-1][j] + dp[i][j-1] : 0;
}
}
return dp[m-1][n-1];
}class Solution {
public int uniquePathsWithObstacles(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
if (grid[0][0] == 0 || grid[m-1][n-1] == 0) {
return 0;
}
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 (grid[i][j] == 1) {
if (i > 0) {
dp[i][j] += dp[i-1][j];
}
if (j > 0) {
dp[i][j] += dp[i][j-1];
}
}
}
}
return dp[m-1][n-1];
}
}def unique_grid_paths(grid):
m, n = len(grid), len(grid[0])
if grid[0][0] == 0 or grid[m-1][n-1] == 0:
return 0
dp = [[0] * n for _ in range(m)]
dp[0][0] = 1
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
if i > 0:
dp[i][j] += dp[i-1][j]
if j > 0:
dp[i][j] += dp[i][j-1]
return dp[m-1][n-1]function uniqueGridPaths(grid) {
if (!grid || grid.length === 0) return 0;
const m = grid.length, n = grid[0].length;
const dp = Array(m).fill().map(() => Array(n).fill(0));
dp[0][0] = grid[0][0] === 1 ? 1 : 0;
for (let i = 1; i < m; i++) {
dp[i][0] = grid[i][0] === 1 ? dp[i-1][0] : 0;
}
for (let j = 1; j < n; j++) {
dp[0][j] = grid[0][j] === 1 ? dp[0][j-1] : 0;
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = grid[i][j] === 1 ? dp[i-1][j] + dp[i][j-1] : 0;
}
}
return dp[m-1][n-1];
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.