Walls and Gates
Fill every empty room with its distance to the nearest gate using one breadth-first search that starts from all the gates at once.
Problem Understanding
Walls and Gates: a grid holds -1 (a wall), 0 (a gate) and INF = 2147483647 (an empty room). Fill each empty room in place with the number of steps to its nearest gate, moving up, down, left or right; leave a room INF if no gate can reach it.
Example: [[INF,-1,0,INF],[INF,INF,INF,-1],[INF,-1,INF,-1],[0,-1,INF,INF]] becomes [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]].
The Intuition: Flood From Every Gate at Once
Asking each room "where is my nearest gate?" means one search per room. Turn it around:
- Put every gate in the queue at distance 0. They all spread together, like ripples starting at once.
- BFS visits cells in order of distance, so the first ripple to touch a room comes from its nearest gate.
- Fill a room once, when it is first reached, and never again. Walls block the ripple.
This is multi-source breadth-first search, the same pattern as Rotting Oranges, where all rotten oranges spread at once, and 01 Matrix, which measures distance to the nearest 0.
Interactive Walkthrough
DARK = WALL · 0 = GATE · ∞ = UNREACHED
QUEUE ALL GATES
queue (front first)
Queue every gate at once: (0, 2), (3, 0). BFS from all of them reaches each room from its nearest gate first
Next
Take (0, 2), distance 0. Fill any neighbouring room that is still INF with 1
rooms
Walls are dark, gates are green and unreached rooms show ∞. Input uses 1 for an empty room. The cell just taken off the queue is outlined, the room it fills is solid, and rooms already filled are tinted with their distance. Try Around a wall to see a room filled by a detour.
Dry Run Table
Input: the example grid; gates at (0,2) and (3,0).
| Taken from queue | Distance | Rooms filled |
|---|---|---|
| (0,2) | 0 | (0,3) = 1, (1,2) = 1 |
| (3,0) | 0 | (2,0) = 1 |
| (0,3) | 1 | none |
| (1,2) | 1 | (1,1) = 2, (2,2) = 2 |
| (2,0) | 1 | (1,0) = 2 |
| (1,1) | 2 | none |
| (2,2) | 2 | (3,2) = 3 |
| (1,0) | 2 | (0,0) = 3 |
| (3,2) | 3 | (3,3) = 4 |
Result: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]].
The Solution Template
Seed the queue with every gate, then a standard BFS that only writes to rooms still at INF.
Walls and Gates Code
1var wallsAndGates = function(rooms) {2 const INF = 2147483647;3 const m = rooms.length, n = rooms[0].length;4 const q = [];5 for (let r = 0; r < m; r++)6 for (let c = 0; c < n; c++)7 if (rooms[r][c] === 0) q.push([r, c]);8 const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];9 let head = 0;10 while (head < q.length) {11 const [r, c] = q[head++];12 for (const [dr, dc] of dirs) {13 const nr = r + dr, nc = c + dc;14 if (nr >= 0 && nr < m && nc >= 0 && nc < n && rooms[nr][nc] === INF) {15 rooms[nr][nc] = rooms[r][c] + 1;16 q.push([nr, nc]);17 }18 }19 }20};
Edge Cases & Common Mistakes
- One BFS per gate: correct only if you keep the minimum, and much slower; seed all gates together instead.
- Overwriting a filled room: only fill cells that are still INF; a later visit is never shorter.
- Walking through gates or walls: the INF check skips both, since neither is INF.
- No gates: the queue starts empty and nothing changes.
- Unreachable rooms: they correctly stay INF.
Summary
Queue every gate, then BFS: each neighbouring room still at INF gets the current distance + 1 and joins the queue. Every room is filled once with its nearest-gate distance. O(m · n) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet