The problem
A grid has walls, gates and empty rooms. Fill each empty room with its distance to the nearest gate (steps up, down, left or right). Rooms that can’t reach a gate stay infinite.
Input: .WG. / ...W / .W.W / GW.. Output: 3 W 0 1 / 2 2 1 W / 1 W 2 W / 0 W 3 4
Picture it
Picture a building plan with exits (gates). Instead of searching from every room, we start a ripple from all exits at once. The ripple spreads one step per round; the first time it reaches a room, that’s the room’s distance to its nearest exit.
How to recognise it
- A grid where every empty cell needs its distance to the nearest target (a gate), not to one fixed target.
- Moves are one step in four directions, and walls block movement, so every step costs the same.
- There are many sources, and each cell wants the closest one.
- With grids up to 250 × 250 you cannot start a fresh search for each of 62,500 cells.
Start with brute force
For every empty room, run its own BFS outwards until it reaches a gate, and write the number of steps.
def gates_brute(rooms):
out = [row[:] for row in rooms]
for r, c in all_cells(rooms):
if rooms[r][c] != INF:
continue
seen, q = {(r, c)}, deque([(r, c, 0)])
while q:
a, b, d = q.popleft()
if rooms[a][b] == 0:
out[r][c] = d
break
for x, y in nbrs(rooms, a, b):
if rooms[x][y] != -1 and (x, y) not in seen:
seen.add((x, y)); q.append((x, y, d + 1))
return out
Each room may explore the whole grid, so time is O((R·C)²): around 4 × 10^9 steps for 250 × 250. Space is O(R·C) per search.
From brute force to the idea
- Find the waste. The rooms near a gate all search the same neighbourhood, and each search stops when it meets a gate, which is the same event seen from the other side.
- Reverse the roles. Instead of each room looking for a gate, let every gate look for rooms. Put all gates in one queue at distance 0.
- Spread together. Pop a cell, and give each empty neighbour (
INF) the valuerooms[r][c] + 1, then queue it. BFS visits cells in order of distance, so the first gate wave to arrive is the nearest one. - The grid is the visited set. A room stops being
INFthe moment it is filled, so it is never filled twice. Walls are-1and gates are 0, so neither is ever overwritten.
The key idea: one BFS from all gates at once gives each room the distance to its nearest gate.
The key idea
Multi-source BFS from all gates; first arrival = shortest distance. O(rows × cols).
Python solution
def walls_and_gates(rooms):
q = deque()
for r, c in all_cells(rooms):
if rooms[r][c] == 0: # a gate
q.append((r, c))
while q: # gates spread together
r, c = q.popleft()
d = rooms[r][c] + 1
for nr, nc in nbrs(rooms, r, c):
if rooms[nr][nc] == INF:
rooms[nr][nc] = d
q.append((nr, nc))
INF = 2**31 - 1 # empty room
def all_cells(g):
return [(r, c) for r in range(len(g))
for c in range(len(g[0]))]
def nbrs(g, r, c): # in-grid neighbours
R, C = len(g), len(g[0])
for nr, nc in ((r+1, c), (r-1, c),
(r, c+1), (r, c-1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, ncLeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O((R·C)²): a BFS per empty room | O(R·C): a visited set per search |
| Multi-source BFS (shown code) | O(R·C): each cell is queued once, with four neighbour checks | O(R·C): the queue and the list from all_cells; results are written into the grid |
Edge cases
- No gates: the queue starts empty, so every room stays
INF. - A room walled off from every gate (
[[INF,-1,0]]): staysINF. - Only gates or only walls: nothing changes.
- A gate next to a room (
[[0,INF,INF]]): becomes[[0,1,2]]. - The function returns
Noneand editsroomsin place. - Imports and constants:
dequemust be imported, andINF = 2**31 - 1is defined after the function in the shown code, which works because it is looked up when the function runs.
Common mistakes
- Running a BFS from each room instead of from the gates.
- Running separate BFS passes from each gate in turn, which needs min-merging and is slower.
- Testing
rooms[nr][nc] != -1instead of== INF, which overwrites gates and earlier answers and can loop forever. - Writing a constant 1 instead of the parent's distance plus one.
- Treating walls as passable.
You get a matrix of 0s and 1s with no walls. Return a new matrix where each cell holds its distance to the nearest 1 (an original 1 gets 0). Describe what changes, then write it if you like.
Compare with our answer
It is the same multi-source BFS, with the 1s as the gates. A separate dist matrix filled with -1 serves as the visited marker, so the input stays unchanged.
def nearest_one(m):
R, C = len(m), len(m[0])
dist = [[-1] * C for _ in range(R)]
q = deque()
for r, c in all_cells(m):
if m[r][c] == 1:
dist[r][c] = 0
q.append((r, c))
while q:
r, c = q.popleft()
for nr, nc in nbrs(m, r, c):
if dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))
return dist
Time O(R·C), space O(R·C). If the matrix has no 1 at all, every distance stays -1.
A strong answer mentions: starting from all the 1s together, a separate distance matrix as the visited set, and the O(R·C) bound.
1. A city grid marks fire stations and blocked streets. For every open junction you must find the walking distance to the closest station. Which approach fits best?
All steps cost the same, so one BFS from all stations together reaches each junction first from its nearest station. A search per junction repeats work, and sorting ignores blocked streets.
2. Why is the first value written into a room guaranteed to be its shortest distance?
Every queue level is one step further from the gates than the one before. The code never compares values: a room is written once, while it is still INF.
3. A learner changes d = rooms[r][c] + 1 to d = 1. Which input still gives the right answer?
The change makes every room reachable from a gate get 1. That is right only when every room is directly next to a gate, as in the two-cell input. In the other inputs some room is two or more steps away.
Score 60% or more and the lesson is marked complete.