Walls and Gates

Difficulty: Medium Source: NeetCode

Problem

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

• -1 — a wall or an obstacle
• 0 — a gate
• 2147483647 (INF) — an empty room

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

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

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Multi-source BFS — starting BFS from multiple source nodes simultaneously
• BFS level-by-level — BFS naturally computes shortest distances from sources

1. Brute Force (BFS from each empty room)

Intuition

For each empty room, run a BFS to find the nearest gate. This works but is wasteful — each room does its own BFS traversal, leading to O(M * N) BFS runs each costing O(M * N).

Algorithm

1. For each empty room (r, c), run BFS outward until you find a gate.
2. Record the distance to the nearest gate.
3. This is correct but slow.

Solution

from collections import deque

def wallsAndGates(rooms: list[list[int]]) -> None:
    INF = 2147483647
    rows, cols = len(rooms), len(rooms[0])

    def bfs_from(r, c):
        queue = deque([(r, c, 0)])
        visited = {(r, c)}
        while queue:
            row, col, dist = queue.popleft()
            if rooms[row][col] == 0:
                return dist
            for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                nr, nc = row + dr, col + dc
                if 0 <= nr < rows and 0 <= nc < cols and (nr,nc) not in visited and rooms[nr][nc] != -1:
                    visited.add((nr, nc))
                    queue.append((nr, nc, dist + 1))
        return INF

    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == INF:
                rooms[r][c] = bfs_from(r, c)


INF = 2147483647
rooms = [[INF, -1, 0, INF],[INF, INF, INF, -1],[INF, -1, INF, -1],[0, -1, INF, INF]]
wallsAndGates(rooms)
for row in rooms:
    print(row)
# [[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]

Complexity

• Time: O(M²N²) — one BFS per empty room
• Space: O(M * N)

2. Multi-Source BFS (Optimal)

Intuition

Flip the problem: instead of searching outward from each room to find a gate, start from all gates simultaneously and spread outward. In BFS, the first time you reach an empty room, you’ve found the shortest distance to any gate. Multi-source BFS handles this perfectly — enqueue all gates at distance 0, then BFS normally; each room gets assigned the correct distance the first time BFS reaches it.

Algorithm

1. Collect all gate positions and enqueue them all at once.
2. Run BFS: for each cell dequeued at distance d, try all 4 neighbors.
   • If a neighbor is an empty room (INF), set its distance to d + 1 and enqueue it.
   • Walls (-1) and already-visited cells are skipped.
3. In-place modification — update rooms directly.

Solution

from collections import deque

def wallsAndGates(rooms: list[list[int]]) -> None:
    INF = 2147483647
    rows, cols = len(rooms), len(rooms[0])

    queue = deque()
    # Seed BFS with all gate positions
    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))


INF = 2147483647
rooms = [[INF, -1, 0, INF],[INF, INF, INF, -1],[INF, -1, INF, -1],[0, -1, INF, INF]]
wallsAndGates(rooms)
for row in rooms:
    print(row)
# [[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]

# Edge case: no gates
rooms2 = [[INF, INF], [INF, INF]]
wallsAndGates(rooms2)
print(rooms2)  # [[2147483647, 2147483647], [2147483647, 2147483647]]

Complexity

• Time: O(M * N) — each cell is processed at most once
• Space: O(M * N) — queue can hold all cells in the worst case

Common Pitfalls

Starting BFS from rooms instead of gates. The multi-source BFS must start from gates (cells with value 0), not from empty rooms. Gates are the sources of shortest distances.

Updating the distance using the current cell’s value. Since BFS propagates outward by 1 at each step, rooms[nr][nc] = rooms[r][c] + 1 correctly assigns the distance. This works because gates start at 0.

Checking INF before enqueuing. Only enqueue cells that are currently INF — this acts as the “visited” check. Walls (-1) and gates (0) should not be re-processed.