Walls and Gates

PracticeNeetCode ↗LeetCode ↗

Given a 2D grid where -1 is a wall, 0 is a gate, and 2147483647 represents an empty room, fill every empty room with the distance to its nearest gate. Rooms that can't reach any gate stay unchanged.

Example

Key Pointers

• Instead of running BFS outward from every room individually, run one multi-source BFS starting from all gates at once.
• Starting the queue with every gate simultaneously means the BFS naturally expands the nearest gate's reach first — the first time a room is visited, it's already at its true shortest distance.
• Walls simply block the BFS from spreading through them, same as any grid maze traversal.

Step-by-Step Analysis

1. Find every gate (a cell with value 0) and enqueue it.
2. Pop a cell and look at its four neighbors.
3. If a neighbor is still an empty room, set its distance to the current cell's distance + 1 and enqueue it.
4. Repeat until the queue is empty — every reachable room now holds its shortest distance to a gate.

Complexity

Time: O(rows · cols) — Space: O(rows · cols)

Code

from collections import deque

def wallsAndGates(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):
        for c in range(cols):
            if rooms[r][c] == 0:
                queue.append((r, c))

    while queue:
        r, c = queue.popleft()
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            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))

Code Explanation

How the solution above works, piece by piece.

1. Put every gate (value 0) in the queue at the start: a multi-source BFS.
2. Pop a cell and look at its 4 neighbours.
3. A neighbour that is still INF (an empty room nobody reached yet) gets rooms[r][c] + 1 and is queued.
4. Walls (−1) and already-filled rooms are never INF, so they're skipped automatically; no separate visited set is needed.
5. Each cell is filled at most once: O(rows × cols) time.

Visual Walkthrough

Running it on an example grid with one gate at (0, 0):

Video Explanation

NeetCode — Multi-Source BFS, LeetCode 286