Every empty room wants “distance to the nearest gate”, not distance to a specific gate. That framing is the hint: instead of searching outward from each room individually, search outward from all gates at once. A multi-source BFS naturally computes, layer by layer, the shortest distance from the nearest of several starting points — which is exactly what’s needed here. (The shared GridVisualizer only understands binary 0/1 land-and-water grids, and this problem’s state is three-valued (-1 / 0 / INF growing into distances), so the optimal solution below owns a small folder-local visualizer that renders the board and the live BFS queue.)
BFS From Every Empty Room
Time O((m·n)²)Space O(m·n)For each empty room, run its own BFS outward (through non-wall cells) until a gate is found, and record that distance. Correct, but every room repeats work that overlaps heavily with its neighbors’ searches.
from collections import deque
class Solution: def wallsAndGates(self, rooms: list[list[int]]) -> None: if not rooms: return rows, cols = len(rooms), len(rooms[0]) INF = 2147483647
def bfs_distance(sr, sc): visited = {(sr, sc)} queue = deque([(sr, sc, 0)]) while queue: r, c, d = queue.popleft() if rooms[r][c] == 0: return d for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc = r + dr, c + dc if ( 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] != -1 and (nr, nc) not in visited ): visited.add((nr, nc)) queue.append((nr, nc, d + 1)) return INF
original = [row[:] for row in rooms] for r in range(rows): for c in range(cols): if original[r][c] == INF: rooms[r][c] = bfs_distance(r, c)Why it’s correct: BFS explores in order of increasing distance, so the first gate it reaches from a given room is genuinely the nearest one. Complexity: in the worst case (few gates, many empty rooms) each of the O(m·n) empty rooms can trigger a BFS that visits O(m·n) cells, giving O((m·n)²) time — badly redundant, since neighboring rooms’ BFS trees overlap almost entirely.
Multi-Source BFS From All Gates
OptimalTime O(m·n)Space O(m·n)Flip the direction of search: start a single BFS with every gate already in the queue at distance 0. The first time BFS reaches any empty room, that distance must be optimal, because BFS expands in non-decreasing distance order and this room is only reachable this early from some gate — the nearest one.
from collections import deque
class Solution: def wallsAndGates(self, rooms: list[list[int]]) -> None: if not rooms: return rows, cols = len(rooms), len(rooms[0]) INF = 2147483647
queue = deque( (r, c) for r in range(rows) for c in range(cols) if rooms[r][c] == 0 )
while queue: r, c = queue.popleft() for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == INF: rooms[nr][nc] = rooms[r][c] + 1 queue.append((nr, nc))Queue seeded with both gates (0,2) and (3,0) at distance 0 — watch the double-front wave: each pop rings the cell being drained, its still-INF neighbors get stamped dist + 1 and pushed, and no room is ever stamped twice:
Queue · next pop first
The example grid: 5 walls (`-1`) that block all movement, 2 gates (`0`, emerald), and 9 empty rooms carrying `INF`. The queue is seeded with both gates — `(0,2)` then `(3,0)`, the scan order the code finds them in — each at distance 0. Watch the two fronts grow in lockstep: every pop rings its cell, stamps its still-`INF` neighbors with `dist + 1`, and pushes them, and no room is ever stamped twice.
The board above ends exactly at the expected output, [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]. The corner (0,0) locks in 3 along the bottom gate’s corridor (3,0) → (2,0) → (1,0) → (0,0), while the top gate’s path through (1,1) would have reached it at 4 — so the first stamp is provably the smaller distance. That is the guarantee BFS from all gates at once provides: each room locks in the smaller of its distances to any gate the first time it is reached, and the rooms[nr][nc] == INF guard is what prevents a later, longer stamp from ever overwriting it.
Why it’s correct: BFS visits cells in strictly non-decreasing order of distance from the set of sources (all gates simultaneously). The first time a room is reached and assigned a distance, no shorter path from any gate can exist, since anything shorter would have been dequeued earlier. Complexity: every cell is enqueued and dequeued at most once, doing O(1) work per neighbor → O(m·n) time, O(m·n) space for the queue in the worst case, a large improvement over re-running BFS from every room.