← Visualizers
Graphs · Multi-source BFS LeetCode 542

01 Matrix / visualized

The instinct is to stand on each 1 and walk until you find a 0 — one whole queue per cell, which is O((mn)²). Turn it round: put every 0 in the queue before the first pop and a single sweep hands every cell its distance to the nearest source. This is not reachability — every cell is reached; the question is how far. There is a genuinely different correct machine here too, the two-pass DP, and watching its one-pass cousin fail is the shortest argument for why BFS is the safer default.

Execution

idle
INVARIANT Multi-Source Distance Invariant: Don't search for 0 from every 1 (O((mn)²)). Seed EVERY 0 into the queue at t=0 (dist=0). Concentric waves radiate outward; first time a cell is reached is guaranteed its shortest distance to ANY 0!
Press Run to begin.
0 / 0
Speed

Java · running line

BFS
the cell being handled in the queue / just explored a 0 — a source, distance 0 settled distance not reached — still ∞
INTERVIEW SCRIPT

How to Explain 01 Matrix to an Interviewer

1. Reject the $O((mn)^2)$ Forward Instinct

"Searching for the nearest 0 from every 1 triggers $O(m \cdot n)$ separate BFS traversals, wasting $O((m \cdot n)^2)$ time."

2. Multi-Source Inversion

"Seed all zeros into the queue at $t=0$ with dist[r][c] = 0, and initialize all 1s with -1. Concentric waves radiate outward simultaneously."

3. First Reach = Global Shortest Distance

"Because BFS processes nodes in increasing distance order, the first time wave $d$ touches cell (nr, nc), its shortest distance to ANY 0 is guaranteed to be $d$."

4. Two-Pass DP Alternative

"We can also solve in $O(1)$ extra space via DP: Pass 1 sweeps top-to-bottom & left-to-right (from top/left neighbors), and Pass 2 sweeps bottom-to-top & right-to-left (from bottom/right neighbors)."

BFS: O(m·n) time, O(m·n) queue  ·  two-pass DP: O(m·n) time, O(1) extra  ·  one BFS per 1: O((m·n)²)
Seeding every 0 at once is the same inversion LC 130 makes with the border: ask the sources the question, not the cells. The two-pass DP is correct and cheaper on memory, but it is correct only because both sweeps run — and nothing in the code tells you when you have written just one. BFS has no half-correct form, which is why it is the safer default.