Walls and Gates — Multi-Source BFS Every FAANG Grid Interview Tests

Problem Statement#

You are given an m x n grid rooms initialized with three possible values: -1 for a wall or obstacle, 0 for a gate, and INF (we use 2^31 - 1 = 2147483647) for an empty room. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, leave it as INF.

Constraints:

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

Example 1:

Input:
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

Example 2:

Input:  rooms = [[-1]]
Output: [[-1]]
Explanation: No empty rooms; output is unchanged.

Example 3:

Input:  rooms = [[0, INF]]
Output: [[0, 1]]
Explanation: The room at (0,1) is one step from the gate at (0,0).

Why This Problem Matters#

Walls and Gates is the canonical example of multi-source BFS — a technique that comes up repeatedly at Amazon, Google, and Microsoft grid interviews. The naive approach (BFS from every empty room independently) is O((m*n)^2), which is far too slow for a 250x250 grid. The interview is not really asking you to fill distances; it is asking whether you recognize that BFS from multiple sources simultaneously produces the same correct result in O(m*n) time.

This problem also trains you to think "backwards" from the goal. Instead of asking "from each room, how far is the nearest gate?" you reframe it as "starting from every gate at once, how far can I push the wave front?" The two questions have identical answers, but the second is dramatically cheaper to compute. This reversal is a pattern that appears in LC 417 (Pacific Atlantic), LC 1162 (As Far from Land), and LC 542 (01 Matrix).

If you have already solved 01 Matrix (LC 542) the structure here is identical: just replace "all zeros" with "all gates" and "update all ones" with "update all INF rooms". Seeing that connection in an interview signals strong pattern recognition.

The Core Insight#

Every BFS from a single source computes shortest distances from that source. When you have multiple sources and each destination only cares about the nearest source, running BFS from all sources simultaneously is equivalent to imagining a virtual super-source connected to every real source with distance 0. The BFS wavefront from the super-source gives each destination its distance to the nearest real source.

For Walls and Gates: enqueue all gate cells at distance 0. When the BFS processes a gate cell, it tries to propagate to adjacent empty rooms. If the adjacent room is still INF, it has not been reached before, so the current distance is the shortest possible. Mark it and enqueue it. Walls (-1) are simply ignored.

The correctness guarantee is the same as standard BFS: because BFS processes cells in non-decreasing distance order, the first time any room is reached, it is reached by the shortest path.

Visual Dry Run#

Input grid (INF shown as ∞):

∞  -1   0   ∞
∞   ∞   ∞  -1
∞  -1   ∞  -1
0  -1   ∞   ∞

Step 0 — Enqueue all gates at distance 0: Queue: [(0,2), (3,0)]

Step 1 — Process (0,2) dist=0: neighbors (0,1) is -1 skip, (0,3) is INF → set 1 and enqueue, (1,2) is INF → set 1 and enqueue. Process (3,0) dist=0: neighbors (2,0) is INF → set 1, (3,1) is -1 skip.

Grid after step 1:

∞  -1   0   1
∞   ∞   1  -1
1  -1   ∞  -1
0  -1   ∞   ∞

Step 2 — Process (0,3) dist=1, (1,2) dist=1, (2,0) dist=1:

• (0,3) → no valid INF neighbors
• (1,2) → (1,1) INF → set 2, (1,3) is -1 skip, (2,2) INF → set 2
• (2,0) → (1,0) INF → set 2

Step 3 — Continue BFS; final grid:

3  -1   0   1
2   2   1  -1
1  -1   2  -1
0  -1   3   4

The bottom-right corner (3,3) = 4 because it takes 4 steps from the gate at (3,0), going around walls.

Common Mistakes#

1. BFS from each room independently. The naive O((m*n)^2) approach starts a fresh BFS for every INF room. For a 250x250 grid that is 62 500 BFS runs, each potentially visiting 62 500 cells — over 3 billion operations. Always multi-source from gates.

2. Checking rooms[nr][nc] == INF as the visit condition but using a wrong sentinel. The problem defines INF as 2^31 - 1. If you check > 0 or != -1 as your "is empty room" condition, you will also process already-updated rooms (with dist 1, 2, ...) and corrupt answers. Only propagate into cells that are still exactly INF.

3. Forgetting the early termination: no gates exist. If the grid has no gates, every room should stay INF. The multi-source approach handles this naturally because the queue starts empty and the BFS loop never executes. But if you add special handling before the loop, be careful not to accidentally reset the grid.

4. Modifying walls. Some candidates propagate into -1 cells and then check if the value changed. Always add an explicit check rooms[nr][nc] == INF before enqueueing. Walls must never be updated.

5. Using DFS instead of BFS. DFS does not guarantee shortest paths. A DFS from gate A might write distance 5 to a room that gate B can reach in distance 1. BFS is mandatory for shortest-distance problems.

6. Enqueueing the same room multiple times. The visited check (rooms[nr][nc] == INF) must happen before you enqueue, not after you dequeue. If you enqueue first and check later, the same cell can be enqueued multiple times with different distances, causing incorrect results and performance degradation.

Solutions#

Python#

from collections import deque
 
def wallsAndGates(rooms: list[list[int]]) -> None:
    # Modify rooms in-place — no return value needed
    if not rooms:
        return
 
    ROWS, COLS = len(rooms), len(rooms[0])
    INF = 2 ** 31 - 1
 
    # Step 1: seed the queue with every gate cell
    queue = deque()
    for r in range(ROWS):
        for c in range(COLS):
            if rooms[r][c] == 0:          # gate found
                queue.append((r, c))      # enqueue at distance 0
 
    # Step 2: multi-source BFS — expand wave front outward
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        row, col = queue.popleft()        # process cell in FIFO order
 
        for dr, dc in directions:
            nr, nc = row + dr, col + dc   # candidate neighbor
 
            # Only propagate into cells that are still unreached empty rooms
            if 0 <= nr < ROWS and 0 <= nc < COLS and rooms[nr][nc] == INF:
                # Distance is one more than the current cell's distance
                rooms[nr][nc] = rooms[row][col] + 1
                queue.append((nr, nc))    # enqueue for further expansion

JavaScript#

var wallsAndGates = function(rooms) {
    // Edge case: empty grid
    if (!rooms || rooms.length === 0) return;
 
    const ROWS = rooms.length;
    const COLS = rooms[0].length;
    const INF = 2 ** 31 - 1;
 
    // Step 1: collect all gate positions as BFS seeds
    const queue = [];
    for (let r = 0; r < ROWS; r++) {
        for (let c = 0; c < COLS; c++) {
            if (rooms[r][c] === 0) {   // gate cell
                queue.push([r, c]);    // start BFS from here
            }
        }
    }
 
    // Step 2: BFS outward from all gates simultaneously
    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    let head = 0;                       // use index instead of shift() for O(1) dequeue
 
    while (head < queue.length) {
        const [row, col] = queue[head++]; // dequeue next cell
 
        for (const [dr, dc] of directions) {
            const nr = row + dr;
            const nc = col + dc;
 
            // Skip out-of-bounds, walls, or already-visited rooms
            if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS) continue;
            if (rooms[nr][nc] !== INF) continue; // already set or is a wall
 
            // Set distance: one more than current cell
            rooms[nr][nc] = rooms[row][col] + 1;
            queue.push([nr, nc]);       // expand from this new room next
        }
    }
};

Complexity Analysis#

The multi-source BFS is optimal because every cell is enqueued at most once (the == INF guard prevents re-enqueueing), and each enqueue/dequeue is O(1). Total work is proportional to the number of cells.

Follow-up Questions#

Q: What if gates can also be surrounded by walls — does that change anything? No. The algorithm naturally handles it: gates that are completely walled off still seed the queue at distance 0, but their BFS expansion will immediately be blocked. Rooms unreachable from any gate will remain INF.

Q: What if we want to find the room farthest from all gates? Run the same multi-source BFS. The last room to be dequeued (or the room with the highest non-INF distance at the end) is the farthest reachable room. This is exactly the "As Far from Land as Possible" pattern (LC 1162).

Q: How would you adapt this if movement costs varied (weighted grid)? Standard BFS assumes uniform cost. For weighted grids you would use Dijkstra's algorithm with a min-heap, seeded with all gates at priority 0.

Q: Can you solve this with DFS? DFS cannot guarantee shortest distances. You could run DFS from each gate and update rooms with min(current, newDist), but this is O((m*n)^2) and has messy revisiting logic. BFS is the right tool.

This Pattern Solves#

• LC 542 — 01 Matrix (distance to nearest 0)
• LC 1162 — As Far from Land as Possible
• LC 994 — Rotting Oranges
• LC 1765 — Map of Highest Peak
• LC 417 — Pacific Atlantic Water Flow (reverse BFS from borders)

Key Takeaways#

• Multi-source BFS: seed the queue with all gates at distance 0 simultaneously — BFS then expands outward, so each empty room is reached in shortest-distance order
• Flip the search direction: instead of BFS from each room to find the nearest gate (O(rooms * gates)), BFS from all gates at once (O(rooms + gates))
• Mark a room visited by writing its distance in-place — no separate visited set needed since the grid itself records the result
• BFS guarantees that the first time a cell is reached, the distance is minimal — no revisiting needed
• Initialize the queue with every 0 cell before scanning for INF cells; the order of gate discovery does not matter
• This multi-source seeding pattern applies to LC 542 (01 Matrix), LC 994 (Rotting Oranges), and any "nearest source" grid problem
• Amazon and Google use this problem to distinguish candidates who know multi-source BFS from those who naively run BFS per room