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.
In 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.
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.
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."
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.
from collections import dequeclass Solution: def wallsAndGates(self, rooms: List[List[int]]) -> None: if not rooms: # (1) return rows, cols = len(rooms), len(rooms[0]) INF = 2147483647 # (2) queue = deque() # (3) for r in range(rows): # seed every gate for c in range(cols): if rooms[r][c] == 0: # (4) queue.append((r, c)) while queue: # (5) r, c = queue.popleft() # (6) 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: # (7) rooms[nr][nc] = rooms[r][c] + 1 # (8) one further than here queue.append((nr, nc))
ts
function wallsAndGates(rooms: number[][]): void { if (!rooms.length) return; // (1) const rows = rooms.length, cols = rooms[0].length; const INF = 2147483647; // (2) const queue: Array<[number, number]> = []; // (3) for (let r = 0; r < rows; r++) for (let c = 0; c < cols; c++) if (rooms[r][c] === 0) queue.push([r, c]); // (4) let head = 0; // index instead of shift() while (head < queue.length) { // (5) const [r, c] = queue[head++]; // (6) 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) { // (7) rooms[nr][nc] = rooms[r][c] + 1; // (8) 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.
(2) The value the problem uses for "an empty room not yet given a distance". It is the largest 32-bit whole number, 2^{31} - 1.
(3) A queue for a breadth-first search.
(4) Every gate goes into the queue at the start. All gates spread outward at the same time. A room is then reached first by its nearest gate, because breadth-first search reaches everything one step away before anything two steps away.
(5) Keep going until no room is left to spread from.
(6) Take the next cell. In TypeScript, the queue is a plain array with a head position, because shift() on a JavaScript array is slow.
(7) A neighbour on the map that is still an unvisited empty room. Walls are −1 and gates are 0, so neither equals INF, and both are skipped.
(8) Its distance is one more than this cell's. Writing the distance also marks the room as visited, so it is never given a second, larger distance. Then it joins the queue.
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).
"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.