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   4

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 naive approach is a BFS from every room to find its nearest gate — $O((rows \times cols)^2)$ . The fix is the reversal you have now seen three times: search from the gates instead, all at once.

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

PythonTypeScript

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))

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.

Complexity

$O(rows \times cols)$ time — each cell is written once and enqueued once.

$O(rows \times cols)$ space for 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.

4.20.7 — Walls and Gates ​

The problem ​

The pattern ​

The solution ​

Complexity ​

Where this goes next ​

What the interviewer will push on ​