01 Matrix LeetCode 542 — BFS Guide

LeetCode 542 — 01 Matrix — gives you an m x n binary matrix where each cell is either 0 or 1. Your task is to return a new matrix of the same dimensions where each cell contains the distance to the nearest 0. Distance is measured in horizontal and vertical steps (Manhattan distance along grid edges, no diagonals).

The problem guarantees that at least one 0 exists in the matrix, so every cell has a valid nearest 0. For a cell that already contains 0, the distance is trivially 0. For 1-cells, you need to find the shortest path to any 0 through adjacent cells.

This is a classic shortest-path problem on an unweighted grid. The naive approach of running BFS from every 1-cell to find its nearest 0 is O((m*n)^2) in the worst case — far too slow for the given constraints of up to 10^4 total cells. The efficient solution runs in O(m*n) using multi-source BFS.

The key insight is to flip the direction of BFS. Instead of asking "from each 1-cell, how far is the nearest 0?", ask "from all 0-cells simultaneously, how far can the BFS wave reach?" Enqueue every 0-cell at distance 0, then run BFS outward. The first time the wavefront reaches any 1-cell, that distance is guaranteed to be the shortest distance to any 0.

This works because BFS explores layer by layer — all cells at distance 1 before distance 2, all cells at distance 2 before distance 3, and so on. When multiple 0-sources expand simultaneously, the wavefronts merge naturally. A 1-cell is settled the moment any wavefront first touches it, and that distance is minimal by BFS correctness.

The result is that every cell is processed exactly once — when it is first dequeued — giving O(m*n) total time. This is a dramatic improvement over the naive O((m*n)^2) approach and is the standard textbook solution for this type of multi-source shortest distance problem.

Before running BFS, set up the result matrix by initializing every 0-cell to distance 0 and every 1-cell to infinity (or a large sentinel like m+n, which is the maximum possible distance in an m x n grid). This initialization serves two purposes: it populates the answer for 0-cells, and it marks 1-cells as unvisited.

Next, enqueue every 0-cell into the BFS queue. These are your starting sources. Marking 0-cells in the result matrix (with value 0) before BFS begins also acts as a "visited" marker — when BFS tries to enqueue their neighbors, it checks whether the neighbor's distance can be improved and skips already-settled cells.

This setup is O(m*n) — one pass to initialize the result matrix and identify all 0-cells. The BFS then begins with a pre-populated queue of all sources, ready to expand in every direction simultaneously from the very first BFS step.

Dequeue cells one at a time. For each dequeued cell (r, c) with distance d, examine all four neighbors (r±1, c) and (r, c±1). If a neighbor is in bounds and its current distance in the result matrix is greater than d+1, update it to d+1 and enqueue the neighbor. This is the standard BFS relaxation step.

Because BFS processes cells in non-decreasing order of distance, the first time a cell is dequeued its distance is final — just like Dijkstra on an unweighted graph. Cells are never re-enqueued once their distance is set because a later path would be at least as long, never shorter.

The queue drains completely when every reachable 1-cell has been settled. At that point, the dist matrix contains the answer for every cell. Cells that were never enqueued are 0-cells (already initialized to 0). Every 1-cell has been reached by the wavefront from its nearest 0-source.

The naive approach runs BFS from each 1-cell individually to find its nearest 0. In the worst case — a large matrix of all 1s except one corner 0 — every 1-cell runs a BFS that traverses the entire m*n grid. With up to m*n cells each doing O(m*n) BFS work, the total complexity is O((m*n)^2), which is 10^8 operations for a 10^4-cell matrix.

Multi-source BFS avoids this explosion by processing each cell exactly once across the entire algorithm. The BFS queue drains after at most m*n dequeue operations, each doing O(1) work per neighbor. Total time is O(4*m*n) = O(m*n). Space is O(m*n) for the queue and result matrix.

The key reason multi-source works is that BFS from all 0s simultaneously never needs to revisit a cell. Once a 1-cell is settled by the nearest 0-wavefront, no other wavefront can improve that distance. This "once settled, always optimal" property is what collapses O((m*n)^2) to O(m*n).

In Python, use collections.deque for O(1) popleft(). Initialize dist as a 2D list with 0 for 0-cells and float("inf") for 1-cells. Append all 0-cells to the deque, then enter the BFS loop: while deque is non-empty, popleft a cell, check all 4 neighbors, update and append if dist[nr][nc] > dist[r][c] + 1. Return dist. Total: ~15 lines.

In Java, use ArrayDeque<int[]> where each int[] is {row, col}. Initialize a 2D int[][] dist array with 0 for 0-cells and Integer.MAX_VALUE for 1-cells. Offer all 0-cells to the queue, then poll in a while loop, expanding 4 directions. If dist[nr][nc] > dist[r][c] + 1, update and offer. Return dist. Total: ~25 lines including bounds checks.

Both implementations are O(m*n) time and O(m*n) space. The deque queue at peak holds at most m*n cells. The dist matrix serves as both the answer and the visited tracking mechanism — no separate visited array is needed because any cell with dist < infinity has been visited.

Walls and Gates (LeetCode 286) is structurally identical to 01 Matrix: multi-source BFS from all gates (value 0) outward to fill all rooms (value INF) with their distance to the nearest gate. The only difference is the cell values and problem framing. Rotting Oranges (LeetCode 994) uses the same pattern where fresh oranges are the "1-cells" and rotten oranges are the "0-cells" — the answer is the last BFS level.

Shortest Path in Binary Matrix (LeetCode 1091) is a single-source BFS on a grid with 8-directional movement — the same BFS mechanics but from one source. Pacific Atlantic Water Flow (LeetCode 417) uses multi-source DFS/BFS from two sets of boundary cells simultaneously — conceptually related to starting from multiple sources.

The broader pattern is the multi-source shortest distance family: whenever you need shortest distances from any of multiple sources, seed BFS with all sources at once. This family includes nearest exit, nearest cell with value X, and any grid problem where distance to the nearest member of a set is required. Recognizing this pattern converts apparent O((m*n)^2) problems to O(m*n) immediately.