Finding a Path in a 2D Array using TypeScript
You have a grid. Some cells are open (0), some are walls (1). Find a path from the start to the destination. You can move up, down, left, or right.
22 Apr 2024
You have a grid. Some cells are open (0), some are walls (1). Find a path from the start to the destination. You can move up, down, left, or right.
This is a classic BFS/DFS problem that shows up in games, robotics, and map navigation.
The Problem
Given an m x n grid where 0 is passable and 1 is blocked, find a path from (startRow, startCol) to (destRow, destCol).
The Code
I use BFS here because it finds the shortest path.
function isValid(maze: number[][], x: number, y: number): boolean {
return x >= 0 && x < maze.length &&
y >= 0 && y < maze[0].length &&
maze[x][y] === 0;
}
function findPath(
maze: number[][],
startRow: number, startCol: number,
destRow: number, destCol: number
): number[][] | null {
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
const visited = new Set<string>();
const queue: { row: number; col: number; path: number[][] }[] = [];
queue.push({ row: startRow, col: startCol, path: [[startRow, startCol]] });
visited.add(`${startRow},${startCol}`);
while (queue.length > 0) {
const { row, col, path } = queue.shift()!;
if (row === destRow && col === destCol) return path;
for (const [dx, dy] of directions) {
const newRow = row + dx;
const newCol = col + dy;
const key = `${newRow},${newCol}`;
if (isValid(maze, newRow, newCol) && !visited.has(key)) {
visited.add(key);
queue.push({ row: newRow, col: newCol, path: [...path, [newRow, newCol]] });
}
}
}
return null;
}
const maze = [
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 1, 1],
[0, 0, 0, 0, 0],
];
console.log(findPath(maze, 0, 0, 4, 4));
// [[0,0], [1,0], [1,1], [1,2], [2,2], [3,2], [4,2], [4,3], [4,4]]How It Works
BFS explores cells level by level. Every cell at distance 1 is checked before any cell at distance 2. This guarantees the first path found is the shortest.
The visited set prevents revisiting cells, which avoids infinite loops and redundant work.
Complexity
- Time: O(m × n) — each cell visited at most once.
- Space: O(m × n) — for the visited set and queue.
The Trade-off
BFS gives you the shortest path but stores the entire path in the queue, which uses more memory. DFS uses less memory but doesn't guarantee the shortest path.
If you need the shortest path, use BFS. If you just need any path, DFS with backtracking is more memory-efficient. For weighted grids (different movement costs), use Dijkstra's or A*.