Walls and Gates — Multi-Source BFS

Given a grid where 0 = gate, -1 = wall, and INF = empty room, fill each empty room with the distance to its nearest gate.

Why BFS from Gates?

BFS from each room to find the nearest gate is O(m²n²). Instead, start BFS from all gates simultaneously — each room is visited at most once, giving O(mn).

Solution

from collections import deque

def walls_and_gates(rooms):
    """
    Fill rooms with distance to nearest gate (in-place).
    Time: O(m × n), Space: O(m × n)
    """
    if not rooms:
        return

    INF = 2147483647
    rows, cols = len(rooms), len(rooms[0])
    queue = deque()

    # Enqueue all gates
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == 0:
                queue.append((r, c))

    directions = [(0,1), (0,-1), (1,0), (-1,0)]

    while queue:
        r, c = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                and rooms[nr][nc] == INF):
                rooms[nr][nc] = rooms[r][c] + 1
                queue.append((nr, nc))

Trace

Before:                    After:
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

Gates at (0,2) and (3,0) start in the queue. BFS expands level by level:

• Level 0: gates (0,2), (3,0)
• Level 1: (0,3), (1,2), (2,0) get distance 1
• Level 2: (1,1), (1,0) get distance 2
• Level 3: (0,0), (3,2) get distance 3
• Level 4: (3,3) gets distance 4

Why It’s Correct

BFS explores nodes in order of increasing distance from the sources. Since we start from all gates simultaneously, the first time we reach a room, we’ve found the shortest distance to the nearest gate. We only update rooms with value INF, so walls and already-computed rooms are skipped.

Edge Cases

• No gates — all rooms remain INF
• No empty rooms — nothing to fill
• Room surrounded by walls — stays INF (unreachable)
• All gates — all values stay 0

Complexity

Metric	Value
Time	O(m × n) — each cell visited once
Space	O(m × n) — queue can hold all cells

When to Use This Pattern

“Distance to nearest X” problems are always multi-source BFS:

Problem	Sources
Walls and Gates	Gates (value 0)
Rotten Oranges	Rotten cells (value 2)
As Far from Land	Land cells
Map of Highest Peak	Water cells

Related Problems

• Rotten Oranges (LeetCode 994)
• As Far from Land as Possible (LeetCode 1162)
• Shortest Distance from All Buildings (LeetCode 317)
• 01 Matrix (LeetCode 542)