Intermediate LevelData Structures & Algorithms
How do you find the shortest path in an unweighted grid using BFS?
ā Interview Prompt: Find the shortest path in a binary matrix (0=open, 1=blocked) from top-left to bottom-right using BFS.
BFS Level-by-Level guarantees the shortest path in unweighted grids/graphs because it explores all cells at distance $d$ before distance $d + 1$.
Algorithm:
1
Enqueue the start cell with distance 0.
2
For each cell dequeued: explore all 8 directions (or 4 for Manhattan).
3
Enqueue valid unvisited open cells with
distance + 1.4
Return distance when reaching the target.
Code Implementation Example
typescript
function shortestPathBinaryMatrix(grid: number[][]): number {
const n = grid.length;
if (grid[0][0] || grid[n - 1][n - 1]) return -1;
const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
const queue: [number, number, number][] = [[0, 0, 1]]; // [row, col, dist]
grid[0][0] = 1; // mark visited
while (queue.length) {
const [r, c, dist] = queue.shift()!;
if (r === n - 1 && c === n - 1) return dist;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nc >= 0 && nr < n && nc < n && grid[nr][nc] === 0) {
grid[nr][nc] = 1; // mark visited
queue.push([nr, nc, dist + 1]);
}
}
}
return -1;
}š”BFS shortest path in binary matrix with 8-directional movement.
šÆ Interview Key Takeaway
BFS is the correct algorithm for shortest path in unweighted graphs/grids. Dijkstra would also work but is overkill ā BFS is O(V+E) vs O((V+E) log V).
#DSA#BFS#Shortest Path#Grid#Intermediate
Back to all Data Structures & Algorithms Questionsā