Walls and Gates — Multi-Source BFS Queue from Every Gate at Once

Problem Statement#

You are given an m x n grid rooms initialized with these three possible values:

• -1: A wall or an obstacle.
• 0: A gate.
• INF (2147483647): An empty room.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, the value should remain INF.

You must modify the grid in place.

Constraints:

• m == rooms.length, n == rooms[i].length
• 1 <= m, n <= 250
• rooms[i][j] is -1, 0, or 2^31 - 1.

Input:  rooms = [[INF,-1,0,INF],[INF,INF,INF,-1],[INF,-1,INF,-1],[0,-1,INF,INF]]
Output:        [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Why This Problem Matters#

LeetCode 286 Walls and Gates is the canonical "multi-source BFS" interview question and shows up at Amazon, Google, Meta, and Facebook. It is the simpler sibling of Rotting Oranges (LeetCode 994) and 01 Matrix (LeetCode 542). The naive solution — running BFS from every empty room toward the nearest gate — costs O((m times n) squared) and times out. The optimal solution flips the perspective: BFS outward from all gates simultaneously in a single sweep.

Recruiters love this problem because it is small enough to implement in 15 minutes but tests three core skills: grid traversal, queue-based BFS, and recognizing when to reverse the search direction. If you can solve this cleanly, you have demonstrated readiness for harder problems like Pacific Atlantic Water Flow and Shortest Bridge.

The Core Insight#

Instead of asking "for each empty room, what is the nearest gate?", ask "for each gate, expand outward and stamp distances on every reachable room." If we run BFS from a single gate, we fill in shortest distances to every reachable room — but only relative to that gate. If we ran one BFS per gate sequentially, we would need to take the minimum across all gates, costing O((m times n) times G) where G is the number of gates.

The trick is multi-source BFS: seed the queue with every gate at distance 0, then expand in lockstep. Since BFS expands by distance, the first time a room is visited it is by the nearest gate. Mark visited by overwriting INF with the actual distance — this doubles as a visited bitmap and avoids extra storage.

Visual Dry Run#

A 3 by 3 grid with INF as the placeholder:

INF -1   0
INF INF INF
0   -1  INF

Step 0. Queue starts with both gates: (0,2) and (2,0), both at distance 0.

Step 1. Expand (0,2): neighbors (1,2) become 1. Expand (2,0): neighbor (1,0) becomes 1. Queue holds (1,2) and (1,0).

Step 2. Expand (1,2): neighbor (1,1) becomes 2. Expand (1,0): neighbor (1,1) is already 2, skip. Queue holds (1,1).

Step 3. Expand (1,1): neighbor (2,1) is a wall, skip; (0,1) is a wall, skip. Done.

Final grid:

INF -1  0
1   2   1
0   -1  INF

The two INF cells could not be reached and stay INF. The BFS visited each cell at most once thanks to the in-place visited check.

Solution (Optimal)#

We use a deque seeded with all gates. For each dequeued cell, we iterate its four neighbors and update only INF cells.

from collections import deque
from typing import List
 
INF = 2147483647
 
def wallsAndGates(rooms: List[List[int]]) -> None:
    if not rooms or not rooms[0]:
        return
    m, n = len(rooms), len(rooms[0])
    queue = deque()
    for r in range(m):
        for c in range(n):
            if rooms[r][c] == 0:
                queue.append((r, c))
 
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        r, c = queue.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and rooms[nr][nc] == INF:
                rooms[nr][nc] = rooms[r][c] + 1
                queue.append((nr, nc))

const INF = 2147483647;
 
function wallsAndGates(rooms) {
  if (!rooms.length || !rooms[0].length) return;
  const m = rooms.length, n = rooms[0].length;
  const queue = [];
  let head = 0;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (rooms[r][c] === 0) queue.push([r, c]);
    }
  }
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  while (head < queue.length) {
    const [r, c] = queue[head++];
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < m && nc >= 0 && nc < n && rooms[nr][nc] === INF) {
        rooms[nr][nc] = rooms[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
  }
}

Complexity. Time O(m times n) because each cell is enqueued at most once. Space O(m times n) in the worst case for the BFS queue.

Common Mistakes#

• Running BFS from every empty cell toward the nearest gate. This is O((m times n) squared) and times out.
• Using DFS instead of BFS. DFS does not give shortest distances on uniform-cost grids; you would have to retry every gate per cell.
• Forgetting that walls have value -1 and writing if rooms[nr][nc] is not equal to 0. The INF check captures both walls and already-updated cells.
• Marking visited at dequeue time instead of enqueue time, leading to duplicate enqueues.
• Using a Python list as a queue with pop(0) — O(n) per pop, times out on 250 by 250 grids.

Interview Tips#

• Open by stating the brute force and computing its complexity. Recruiters want to see you actively reject inferior approaches.
• Pitch multi-source BFS clearly: "I will seed the queue with every gate up front and let BFS naturally compute the minimum distance to each room."
• Mention that overwriting INF doubles as a visited check, saving an extra m by n boolean array.
• Discuss the difference between BFS for shortest distance on uniform-cost grids versus Dijkstra for weighted grids.
• Mention that in production, this is exactly the algorithm games use for influence maps, threat zones, and pathfinding heatmaps.

Follow-up Questions#

1. What if there are different gate types and you need the nearest gate of each type? Run one BFS per type or use a tuple of distances per cell.
2. What if movement cost varies (water cells cost 2)? Switch to Dijkstra with a priority queue heap.
3. What if you only need the answer for K query cells? If K is small, individual BFS per query may be cheaper; otherwise the multi-source approach wins.
4. What if the grid changes dynamically (gates added or removed)? Recompute incrementally or maintain a layered BFS structure.
5. Could you solve this with two passes of dynamic programming like 01 Matrix? Yes, with two sweeps (top-left to bottom-right, then reverse), but BFS is more general.

Key Takeaways#

• Multi-source BFS is the FAANG signature for "nearest of several sources" grid problems.
• Seed the BFS queue with all sources at distance 0 — distance grows naturally per layer.
• Use the grid itself as the visited marker by writing distances in place.
• A deque with O(1) popleft is mandatory; lists with pop(0) will TLE.
• Time O(m times n), space O(m times n) — optimal for the problem class.
• The same pattern solves Rotting Oranges, 01 Matrix, As Far From Land As Possible, and Shortest Bridge.