TL;DR
Multi-source BFS seeded with every gate at once fills each room with its nearest-gate distance in one sweep — O(m·n) time, O(m·n) space.
Approach 1 — Brute force: BFS from every room
For each empty room, run a fresh BFS until you hit the first gate, and record that distance.
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 nearest_gate(sr: int, sc: int) -> int:
queue = deque([(sr, sc, 0)])
seen = {(sr, sc)}
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 \
(nr, nc) not in seen and rooms[nr][nc] != -1:
seen.add((nr, nc))
queue.append((nr, nc, d + 1))
return INF
for r in range(rows):
for c in range(cols):
if rooms[r][c] == INF:
rooms[r][c] = nearest_gate(r, c)
Complexity: each room’s BFS is O(m·n), and there are up to O(m·n) rooms → O((m·n)²). On a few-hundred-square grid that’s billions of steps — too slow.
Approach 2 — Multi-source BFS (the key idea)
The insight: a room’s answer is its distance to the closest gate. Rather than searching outward from each room, launch the search from all gates simultaneously. Put every gate in the BFS queue at distance 0; then expand the wavefront one ring at a time. Because BFS grows in strict distance order and all gates start together, the first gate whose wave reaches a room is necessarily its nearest — so the first time a room is written, it gets the correct minimum, and we never overwrite it.
This is multi-source BFS: a normal BFS whose queue is pre-loaded with many start nodes instead of one. Using INF itself as the “unvisited” sentinel means we never need a separate visited set — a room is unvisited exactly while it still equals INF.
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()
for r in range(rows):
for c in range(cols):
if rooms[r][c] == 0:
queue.append((r, c))
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))
Walkthrough (example 1, two gates at (0,2) and (3,0)): both gates enter the queue first. Ring 1 fills their orthogonal neighbors with 1 — (0,3), (1,2) from the top gate; (2,0) from the bottom gate. Ring 2 fills the next unvisited neighbors with 2, and so on. A room like (1,1) is reachable from either gate; whichever wavefront arrives first (distance 2) claims it, and the == INF guard blocks the slower wave from overwriting. Walls (-1) are never INF, so the wave flows around them; the lone unreachable room, if any, keeps INF.
Complexity: every cell is enqueued at most once and processed with constant work → O(m·n) time, O(m·n) space for the queue.
DFS alternative (named): you can recurse outward from each gate, writing dist and recursing into neighbors whose current value exceeds dist + 1. It produces correct answers but may rewrite a cell several times as better distances arrive from different gates, and it risks deep recursion on large grids. BFS is preferred here because its distance-ordered expansion writes each cell exactly once — DFS has no such guarantee for shortest distances.
Common pitfalls
- Single-source instead of multi-source. Running BFS from one gate at a time and combining is the slow O((m·n)²) trap — seed all gates before the first pop.
- Overwriting a shorter distance. The
== INF check is what enforces “first write wins.” Drop it and a later, longer wave can clobber the correct value.
- Walls.
-1 is not INF, so the guard already skips walls — don’t accidentally treat every non-zero cell as a room.
- Empty grid. Guard
if not rooms (and implicitly rooms[0]) so len(rooms[0]) doesn’t throw.
Pattern takeaway
When you need the distance from many sources at once to every cell — “nearest gate”, “rot spreading from all rotten oranges”, “distance to closest 0” — use multi-source BFS: initialize the queue with every source at distance 0 and expand one unweighted ring at a time. It collapses what looks like many separate shortest-path searches into a single O(V + E) sweep.