Appearance
4.20.7 — Walls and Gates
LeetCode 286 · Medium
The problem
A grid holds -1 (a wall), 0 (a gate) and INF (an empty room, given as 2^{31}-1). Fill each empty room with the distance to its nearest gate. Rooms that cannot reach any gate stay INF.
INF -1 0 INF 3 -1 0 1
INF INF INF -1 → 2 2 1 -1
INF -1 INF -1 1 -1 2 -1
0 -1 INF INF 0 -1 3 4In plain English, you are given a 2D grid representing a building. -1 cells are walls (impassable). 0 cells are gates (exits). INF (2147483647) cells are empty rooms. For every empty room, you need to replace INF with the length of the shortest path to reach the nearest gate. You can move up, down, left, right. If a room is completely walled off and cannot reach a gate, leave it as INF. The grid is mutated in-place.
The pattern
Exactly 4.20.6 Rotting Oranges with different labels. Gates are the rotten oranges, rooms are the fresh ones, and instead of counting rounds you write the round number into the cell.
The ELI5 Analogy
Imagine being lost in a dark maze with hundreds of rooms, looking for an exit sign. If you start from your room and wander blindly (running a search from every room), you'll waste a lot of time. Instead, imagine someone at every exit gate turns on a super bright flashlight. The light floods down the hallways, bouncing one room at a time. The first time light hits your room, you know the exact shortest distance to the gate because light travels in straight, expanding waves. Multi-source BFS is just "turning on the flashlights at all gates simultaneously."
What about a Brute Force Approach?
The naive approach is a BFS/DFS from every single empty room looking for a gate. If you have a massive grid mostly made of empty rooms, and gates are far away, a search from one room might traverse the entire grid (O(N) operations). If you do this for every empty room (O(N) rooms), you get O(N^2) total operations. On a 250x250 grid, N = 62,500, and N^2 \approx 3.9 billion operations. The reversal (searching from the gates instead) processes every cell exactly once, taking only 62,500 operations.
Multi-source BFS gives every room its distance to the nearest gate in a single pass, because BFS expands in rings and the first ring to reach a room came from the closest gate.
The solution
python
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): # seed every gate
for c in range(cols):
if rooms[r][c] == 0:
queue.append((r, c))
while queue:
r, c = queue.popleft()
for nr, nc in ((r+1,c), (r-1,c), (r,c+1), (r,c-1)):
if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == INF:
rooms[nr][nc] = rooms[r][c] + 1 # one further than here
queue.append((nr, nc))ts
function wallsAndGates(rooms: number[][]): void {
if (!rooms.length) return;
const rows = rooms.length, cols = rooms[0].length;
const INF = 2147483647;
const queue: Array<[number, number]> = [];
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (rooms[r][c] === 0) queue.push([r, c]);
let head = 0; // index instead of shift()
while (head < queue.length) {
const [r, c] = queue[head++];
for (const [nr, nc] of [[r+1,c],[r-1,c],[r,c+1],[r,c-1]] as [number,number][]) {
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && rooms[nr][nc] === INF) {
rooms[nr][nc] = rooms[r][c] + 1;
queue.push([nr, nc]);
}
}
}
}This version is even simpler than Rotting Oranges, because the distance is stored in the grid rather than counted, so there is no need to process the queue level by level. Each cell's value is its parent's value plus one, and that is automatically the ring number.
rooms[nr][nc] == INF does three jobs at once. It rejects walls (-1), rejects gates (0), and rejects rooms already filled in — because a filled room no longer holds INF. That single comparison is the visited check.
Writing the distance is the visited mark, and it happens on enqueue. A room reached by two gates in the same ring would otherwise be queued twice; the first write blocks the second.
Why the first arrival is the nearest gate. BFS processes cells in non-decreasing distance order. A room is written when it is first reached, and any later route to it is at least as long, so no update is ever needed. That is the property that makes BFS the right tool and DFS the wrong one.
In TypeScript, use a head index rather than Array.shift(). shift() is O(n) in principle, which would turn a linear algorithm quadratic on a large grid.
Code Walkthrough & Trace
Consider a 1D grid [0, INF, INF, 0]
| Step | Action | Queue | Grid State |
|---|---|---|---|
| 1 | Initial scan seeds gates. | [(0,0), (0,3)] | [0, INF, INF, 0] |
| 2 | Pop (0,0). Neighbors: (0,1). | [(0,3)] | ... |
| 3 | grid[0][1] is INF. Set to 0 + 1 = 1. Enqueue (0,1). | [(0,3), (0,1)] | [0, 1, INF, 0] |
| 4 | Pop (0,3). Neighbors: (0,2). | [(0,1)] | ... |
| 5 | grid[0][2] is INF. Set to 0 + 1 = 1. Enqueue (0,2). | [(0,1), (0,2)] | [0, 1, 1, 0] |
| 6 | Pop (0,1). Neighbors: (0,0), (0,2). Both are != INF. | [(0,2)] | [0, 1, 1, 0] |
| 7 | Pop (0,2). Neighbors: (0,1), (0,3). Both are != INF. | [] | [0, 1, 1, 0] |
Complexity
O(rows \times cols) time — each cell is written once and enqueued once. To break it down: finding the initial gates takes a single pass over the entire grid, costing O(rows \times cols). During the BFS phase, a cell is pushed to the queue only if its value is exactly INF. When it is pushed, its value is immediately overwritten to a number. Therefore, no cell is ever pushed to the queue more than once. The work inside the while loop is exactly proportional to the number of cells enqueued, making the whole BFS phase O(rows \times cols).
O(rows \times cols) space for the queue. In the absolute worst case, the perimeter of the expanding wave from all gates could equal the total number of cells in the grid, bounding the maximum size of the queue.
Compare with the per-room search at O((rows \times cols)^2).
Where this goes next
The same six lines, relabelled:
| problem | sources | what is written |
|---|---|---|
| Walls and Gates | gates | distance to the nearest gate |
| 01 Matrix | every 0 | distance to the nearest zero |
| Rotting Oranges | rotten oranges | the round number, returned as a total |
| As Far from Land as Possible | land cells | the maximum distance reached |
| Map of Highest Peak | water cells | height, since the constraint is the same as distance |
Learn one of these properly and you have all five. The only differences are what seeds the queue and what you do with the answer.
What the interviewer will push on
"Why not BFS from each room?" O((rows \times cols)^2) against O(rows \times cols). Say both numbers.
"Why does the first arrival give the shortest distance?" BFS visits cells in non-decreasing distance order, so a later route can never be shorter.
"Where is your visited check?" The == INF test, which also handles walls and gates.
"What if edges had different costs?" BFS's guarantee breaks and you need Dijkstra with a priority queue. 4.21.
"What if there were no gates?" The queue starts empty, nothing happens, and every room stays INF — correct, with no special case.
One thing to volunteer: say that the == INF comparison is doing three checks at once. Noticing where a single condition covers several cases is the kind of small observation that makes code both shorter and obviously correct.
Next: 4.20.8 Course Schedule — leaving grids behind for dependencies, cycles, and topological order.