Valid Grid Paths — Problem Statement & Solution Guide
Problem Description
Given a rectangular grid of size m x n and a set of obstacle coordinates, find all distinct paths from the top-left cell to the bottom-right cell. Movement is restricted to either right or down at any point.
Examples
Input
grid = [[0,0,0],[0,1,0],[0,0,0]], m = 3, n = 3
Output
[[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]
Explanation: Step-by-step: We start at the top-left cell (0,0). We can move right to (0,1) or down to (1,0). We explore all paths by backtracking and trying both options. This gives us the correct output.
Input
grid = [[0,0,1],[0,1,0],[0,0,0]], m = 3, n = 3
Output
[]
Explanation: Step-by-step: We start at the top-left cell (0,0). We can move right to (0,1) or down to (1,0). However, the path is blocked by an obstacle at (0,2). We cannot move right from (0,1) because it's blocked. We also cannot move down from (1,0) because it's blocked. Therefore, there are no valid paths and the output is an empty list.
Constraints
- 1 <= m, n <= 20
- 0 <= number of asteroids <= 10
Optimal Approach & Strategy
An optimal approach would be to use a depth-first search (DFS) or backtracking algorithm, which only explores valid paths that avoid asteroids, resulting in a time complexity of O(m*n).
Brute Force Approach
A naive approach would be to generate all possible paths and check each one against the grid to see if it intersects with an asteroid. This results in a time complexity of O(2^(m+n)) due to the exponential number of possible paths.
Verified Code Solutions
function validGridPaths(m, n, obstacles) {
const visited = Array(m).fill(0).map(() => Array(n).fill(false));
const paths = [];
function dfs(r, c, path) {
if (r === m - 1 && c === n - 1) {
paths.push([...path]);
return;
}
if (r < m && c < n && !obstacles.some(([x, y]) => x === r && y === c) && !visited[r][c]) {
visited[r][c] = true;
dfs(r + 1, c, [...path, [r, c]]);
dfs(r, c + 1, [...path, [r, c]]);
dfs(r, c, [...path]); // backtrack to explore other paths
visited[r][c] = false;
}
}
dfs(0, 0, []);
return paths;
}class Solution {
public List<List<Integer>> validGridPaths(int m, int n, int[][] obstacles) {
List<List<Integer>> result = new ArrayList<>();
boolean[][] visited = new boolean[m][n];
for (int[] obstacle : obstacles) {
visited[obstacle[0]][obstacle[1]] = true;
}
backtrack(0, 0, new ArrayList<>(), result, visited);
return result;
}
private void backtrack(int x, int y, List<List<Integer>> path, List<List<Integer>> result, boolean[][] visited) {
if (x == m - 1 && y == n - 1) {
result.add(new ArrayList<>(path));
return;
}
if (!isValid(x, y, visited)) {
return;
}
path.add(Arrays.asList(x, y));
backtrack(x + 1, y, path, result, visited);
backtrack(x, y + 1, path, result, visited);
path.remove(path.size() - 1);
}
private boolean isValid(int x, int y, boolean[][] visited) {
return 0 <= x && x < m && 0 <= y && y < n && !visited[x][y];
}
}def valid_grid_paths(m, n, obstacles):
def is_valid(x, y):
return 0 <= x < m and 0 <= y < n and (x, y) not in obstacles
def backtrack(x, y, path):
if x == m - 1 and y == n - 1:
result.append(path)
return
if not is_valid(x, y):
return
backtrack(x + 1, y, path + [[x, y]])
backtrack(x, y + 1, path + [[x, y]])
result = []
backtrack(0, 0, [])
return resultfunction validGridPaths(m, n, obstacles) {
const visited = Array(m).fill(0).map(() => Array(n).fill(false));
const paths = [];
function dfs(r, c, path) {
if (r === m - 1 && c === n - 1) {
paths.push([...path]);
return;
}
if (r < m && c < n && !obstacles.some(([x, y]) => x === r && y === c) && !visited[r][c]) {
visited[r][c] = true;
dfs(r + 1, c, [...path, [r, c]]);
dfs(r, c + 1, [...path, [r, c]]);
dfs(r, c, [...path]); // backtrack to explore other paths
visited[r][c] = false;
}
}
dfs(0, 0, []);
return paths;
}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.