Shortest Path in Binary Matrix - Solution & Explanation

Problem Overview: Given an n x n binary grid, find the length of the shortest path from the top-left cell to the bottom-right cell. Cells with value 0 are open and 1 are blocked. Movement is allowed in 8 directions (horizontal, vertical, and diagonal). If no path exists, return -1.

Approach 1: Breadth-First Search (BFS) Traversal (Time: O(n²), Space: O(n²))

Treat the grid as an implicit graph where each cell is a node and edges connect the 8 neighboring cells. Start a Breadth-First Search from (0,0) if the cell is open. BFS explores the grid level by level, which naturally finds the shortest path in an unweighted graph. Use a queue to process cells and mark visited cells directly in the grid or with a visited matrix to avoid revisiting. For every cell removed from the queue, iterate through the 8 possible directions and enqueue valid neighbors with distance +1. Because each cell is processed at most once, the traversal runs in O(n²) time with O(n²) space for the queue and visited tracking.

This approach works well because all edges have equal cost. BFS guarantees the first time you reach the bottom-right cell is the shortest path length. The grid structure also keeps the implementation simple since neighbors can be generated using a fixed direction array.

Approach 2: A* Search Algorithm (Time: O(n² log n), Space: O(n²))

The A* algorithm improves practical performance by guiding the search toward the target using a heuristic. Instead of a simple queue, maintain a priority queue ordered by f(n) = g(n) + h(n), where g(n) is the distance from the start and h(n) is a heuristic estimate to the goal. For this problem, the Chebyshev distance works well because diagonal movement is allowed. Each step expands the node with the smallest estimated total distance. In dense grids or large search spaces, A* often explores fewer cells than BFS.

The implementation still iterates over the 8 neighbors for every expanded node and updates distances when a shorter path is found. While the worst-case complexity remains O(n² log n) due to heap operations, the heuristic significantly reduces unnecessary exploration in many cases.

Recommended for interviews: BFS is the expected solution. Interviewers want to see that you recognize the grid as an unweighted graph and immediately apply BFS. Mentioning that the grid can be modeled as a graph and exploring neighbors in 8 directions demonstrates strong fundamentals in matrix traversal and array-based graph problems. A* is a strong follow-up discussion if optimization or pathfinding algorithms come up.