Binary Matrix Shortest Path

Find the shortest clear path from top-left to bottom-right using 8-directional BFS

Binary Matrix

Current Cell

Distance

Queue Size

Shortest Path

BFS Queue

Empty

Click "Step" or "Play" to find the shortest path from (0,0) to (n-1,n-1)

Blocked (1)

Clear (0)

Start

Goal

Current

Visited

Path

Python Code - BFS Approach

                if grid[0][0] != 0 or grid[n-1][n-1] != 0:
            
                    return -1
            
                queue = deque([(0, 0, 1)]) # (row, col, distance)
            
                while len(queue) > 0:
            
                    i, j, dist = queue.popleft()
            
                    if in_bounds and grid[i][j] == 0 and not visited[i][j]:
            
                        visited[i][j] = True
            
                        if i == n-1 and j == n-1: return dist
            
                        for di, dj in directions: # 8 directions
            
                            queue.append((i+di, j+dj, dist+1))
            
                return -1 # no path found

Complexity Analysis

Time Complexity O(m × n) Space Complexity O(m × n)

Time Complexity: O(m × n)

Breakdown

Each cell dequeued at most once
8 neighbors checked per cell: O(1)
Queue operations (enqueue/dequeue): O(1)
Total edges explored: ≤ 8 × m × n

T(m,n) = O(V + E) = O(m×n + 8×m×n) = O(m × n)

Mathematical Intuition

BFS visits vertices in order of increasing distance from the source—a property called "level-order traversal." For unweighted graphs, this guarantees that the first time we reach any vertex, we've found the shortest path. The 8-directional movement treats diagonal steps as having the same cost as orthogonal steps.

Key Insight

BFS is optimal for unweighted shortest paths. For weighted grids, use Dijkstra's algorithm with a priority queue (O(m×n log(m×n))).

Space Complexity: O(m × n)

Breakdown

Queue storage: O(m × n) worst case
Visited/distance array: O(m × n)
Path reconstruction (optional): O(m × n)
Typical queue size: O(min(m, n))

S(m,n) = O(m × n) for visited array + queue

Mathematical Intuition

The visited array prevents revisiting cells and can store distances for path length queries. The queue holds the BFS frontier—at most all cells in worst case, but typically bounded by the perimeter of the explored region, which is O(√(m×n)) for compact shapes.

Key Insight

Bidirectional BFS from both source and destination can reduce explored cells from O(m×n) to O(√(m×n)) in practice by meeting in the middle.