Asteroid Field Navigation — Problem Statement & Solution Guide
Problem Description
You are tasked with charting a safe trajectory through a hazardous asteroid field represented as an M x N grid. Your spacecraft starts at the top-left coordinate (0, 0) and must reach the bottom-right coordinate (M-1, N-1). At each step, you may only move one unit to the right or one unit down. However, certain grid cells contain asteroids that render them impassable. A cell is marked as blocked if its value is 1, and passable if its value is 0. Your objective is to determine the total number of distinct valid paths from the start to the destination that do not traverse any blocked cells. If no such path exists, return 0.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Asteroid Field Navigation"
WHY DOES IT MATTER?
This pattern is essential because it teaches the transition from exponential brute force to polynomial DP, a core skill for optimizing recursive problems. It highlights the importance of identifying overlapping subproblems and optimal substructure, which are foundational to dynamic programming. Mastering this pattern prepares engineers for a wide range of grid-based problems, including pathfinding, resource allocation, and state-space exploration.
OPTIMIZATION CHALLENGE
The key insight is space optimization: since each row's DP values depend only on the previous row and the current left neighbor, a 2D array can be compressed into a 1D array of size N. This reduces space from O(M*N) to O(N), which is critical for large grids where memory is a bottleneck. The trade-off is slightly more complex index management, but the performance gain is significant.
REAL-WORLD CONNECTION
This is analogous to network routing in distributed systems, where packets must navigate through a mesh of servers (grid cells) avoiding failed nodes (asteroids). The DP approach mirrors how routing protocols like OSPF compute shortest paths by aggregating link-state information, ensuring efficient and reliable data delivery even in partially failed networks.
In interviews, always start by clarifying constraints: Is the grid large? Are there negative weights? Are there cycles? If the grid is large and only right/down moves are allowed, DP is optimal. If moves are unrestricted (4-directional), BFS or Dijkstra is needed. Always mention the space optimization to 1D array to demonstrate senior-level thinking.
COMPLEXITY AT A GLANCE
O(M*N)O(N)Core Theory — Why This Approach?
The 'Asteroid Field Navigation' problem is a classic instance of path counting in a grid with obstacles, which fundamentally relies on dynamic programming (DP) or memoized backtracking. The naive recursive backtracking approach explores every possible path from the start (0,0) to the end (M-1, N-1), branching at each cell into 'move right' and 'move down' options. However, this leads to exponential time complexity O(2^(M+N)) because the same subproblems (reaching a specific cell (i,j)) are solved repeatedly without caching. For large grids, this redundancy causes the algorithm to time out, as the number of overlapping subproblems grows exponentially with grid size.
The optimal paradigm shifts from pure backtracking to Dynamic Programming, specifically using a bottom-up tabulation or top-down memoization approach. The core insight is that the number of ways to reach a cell (i,j) is the sum of the ways to reach the cell above it (i-1,j) and the cell to its left (i,j-1), provided the current cell is not blocked. If a cell contains an asteroid (blocked), the number of ways to reach it is zero, and it cannot be used as a stepping stone for subsequent cells. This transforms the problem into a linear scan of the grid, where each cell's value is computed in constant time based on previously computed values.
This approach reduces the time complexity to O(M*N), as each cell is visited exactly once, and the space complexity can be optimized to O(N) by using a 1D array to store only the current row's values, leveraging the fact that the current row depends only on the previous row and the current left neighbor. This space optimization is critical for handling large grids in memory-constrained environments, demonstrating the power of DP state compression.
Interview Questions on This Problem
Q1At a fintech platform optimizing transaction routing, how would you adapt this grid path-counting problem to handle dynamic obstacles that appear and disappear over time?
I would model the grid as a time-dependent graph where each cell (i,j) has a state at each time step. If obstacles are dynamic, a static DP table is insufficient. I would use a BFS or Dijkstra's algorithm on a 3D grid (i, j, t) to find the earliest safe path, or if counting paths is required, I would use memoized recursion with time as an additional dimension. For high-frequency updates, I might employ a segment tree or Fenwick tree to efficiently update obstacle states and recompute path counts incrementally, ensuring O(log(M*N)) updates per obstacle change.
Q2In a high-growth startup building a logistics network, how would you modify this problem to find the minimum cost path instead of counting paths, where each cell has a traversal cost?
I would switch from counting paths to a shortest path problem. If costs are non-negative, Dijkstra's algorithm is appropriate, treating the grid as a graph where nodes are cells and edges have weights equal to the destination cell's cost. If costs can be negative, Bellman-Ford would be needed. For a grid with only right/down moves, a DP approach still works: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + cost[i][j]. This maintains O(M*N) time complexity, but the state now stores the minimum cost rather than the count of paths.
Q3At a global product company, how would you handle a grid where some cells are 'portals' that teleport you to another specific cell, while still counting the number of unique paths?
I would treat portals as additional edges in the graph. The DP recurrence would be modified: dp[i][j] = dp[i-1][j] + dp[i][j-1] + sum(dp[portal_source] for all portals that lead to (i,j)). However, if portals create cycles, simple DP fails. In that case, I would use a graph-based approach with memoized DFS or BFS, detecting cycles and using a visited set to avoid infinite loops. For large grids, I might use a topological sort if the graph is a DAG, ensuring O(V+E) time complexity.
Examples
Input
grid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
Output
2
Explanation: The grid is 3x3 with a blocked cell at (1,1). Path 1: (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2). Path 2: (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2). The direct center path is invalid due to the asteroid at (1,1). Total valid paths = 2.
Input
grid = [[0, 0], [0, 0]]
Output
2
Explanation: In a 2x2 grid with no obstacles, there are exactly two paths: Right then Down, or Down then Right. Both paths are valid. Total valid paths = 2.
Input
grid = [[1, 0], [0, 0]]
Output
0
Explanation: The starting cell (0,0) is blocked by an asteroid. Since the spacecraft cannot start its journey, no valid paths exist. Total valid paths = 0.
Input
grid = [[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Output
10
Explanation: This is a 4x4 grid with a single obstacle at (1,1). Without the obstacle, the total paths would be C(6,3) = 20. We subtract the paths that pass through (1,1). Paths from (0,0) to (1,1) is C(2,1) = 2. Paths from (1,1) to (3,3) is C(4,2) = 6. Invalid paths = 2 * 6 = 12. Valid paths = 20 - 12 = 8? Wait, let's re-calculate via DP. DP[0][0]=1, DP[0][1]=1, DP[0][2]=1, DP[0][3]=1. DP[1][0]=1, DP[1][1]=0 (blocked), DP[1][2]=1, DP[1][3]=2. DP[2][0]=1, DP[2][1]=1, DP[2][2]=2, DP[2][3]=4. DP[3][0]=1, DP[3][1]=2, DP[3][2]=4, DP[3][3]=8. Correction: The output is 8.
Constraints
- 1 <= grid.length <= 200
- 1 <= grid[0].length <= 200
- grid[i][j] is either 0 or 1
- grid[0][0] == 0
- grid[m-1][n-1] == 0
Optimal Approach & Strategy
Use dynamic programming with a 2D or 1D array to store the number of ways to reach each cell, computing each cell's value as the sum of the cell above and the cell to the left, skipping blocked cells. This reduces time complexity to O(M*N) and space to O(N) with 1D optimization.
Brute Force Approach
Use recursive backtracking to explore all possible paths from (0,0) to (M-1,N-1), moving right or down at each step, and count the paths that avoid asteroids. This approach has exponential time complexity O(2^(M+N)) due to repeated subproblems.
Verified Code Solutions
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let p=0;
function countPaths(grid){
const M=grid.length, N=grid[0].length;
if(grid[0][0]===1||grid[M-1][N-1]===1) return 0;
const dp=Array.from({length:M},()=>Array(N).fill(0n));
dp[0][0]=1n;
for(let i=0;i<M;i++){
for(let j=0;j<N;j++){
if(grid[i][j]===1){dp[i][j]=0n;continue;}
if(i>0) dp[i][j]+=dp[i-1][j];
if(j>0) dp[i][j]+=dp[i][j-1];
}
}
return Number(dp[M-1][N-1]);
}
if(data.length){
const M=data[p++]; const N=data[p++];
const grid=Array.from({length:M},()=>Array.from({length:N},()=>data[p++]));
console.log(countPaths(grid).toString());
}#include <bits/stdc++.h>
using namespace std;
long long countPaths(const vector<vector<int>>& grid){
int M=grid.size();
int N=grid[0].size();
if(grid[0][0]==1||grid[M-1][N-1]==1) return 0;
vector<vector<long long>> dp(M, vector<long long>(N,0));
dp[0][0]=1;
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
if(grid[i][j]==1) {dp[i][j]=0; continue;}
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];
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
int M,N; if(!(cin>>M>>N)) return 0; vector<vector<int>> grid(M, vector<int>(N));
for(int i=0;i<M;++i) for(int j=0;j<N;++j) cin>>grid[i][j];
cout<<countPaths(grid)<<"\n"; return 0;}
import java.io.*;
import java.util.*;
public class Main {
static long countPaths(int[][] grid){
int M=grid.length, N=grid[0].length;
if(grid[0][0]==1||grid[M-1][N-1]==1) return 0L;
long[][] dp=new long[M][N];
dp[0][0]=1L;
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
if(grid[i][j]==1){dp[i][j]=0L;continue;}
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];
}
public static void main(String[] args) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
int M=Integer.parseInt(st.nextToken());
int N=Integer.parseInt(st.nextToken());
int[][] grid=new int[M][N];
for(int i=0;i<M;i++){
st=new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) grid[i][j]=Integer.parseInt(st.nextToken());
}
System.out.println(countPaths(grid));
}
}
import sys
def count_paths(grid):
M=len(grid); N=len(grid[0])
if grid[0][0]==1 or grid[M-1][N-1]==1:
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:
dp[i][j]=0
continue
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]
if __name__=="__main__":
data=list(map(int,sys.stdin.read().strip().split()))
if not data:
sys.exit()
it=iter(data)
M=next(it); N=next(it)
grid=[[next(it) for _ in range(N)] for _ in range(M)]
print(count_paths(grid))
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let p=0;
function countPaths(grid){
const M=grid.length, N=grid[0].length;
if(grid[0][0]===1||grid[M-1][N-1]===1) return 0;
const dp=Array.from({length:M},()=>Array(N).fill(0n));
dp[0][0]=1n;
for(let i=0;i<M;i++){
for(let j=0;j<N;j++){
if(grid[i][j]===1){dp[i][j]=0n;continue;}
if(i>0) dp[i][j]+=dp[i-1][j];
if(j>0) dp[i][j]+=dp[i][j-1];
}
}
return Number(dp[M-1][N-1]);
}
if(data.length){
const M=data[p++]; const N=data[p++];
const grid=Array.from({length:M},()=>Array.from({length:N},()=>data[p++]));
console.log(countPaths(grid).toString());
}
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.