LeetCode 286: Walls and Gates

Problem Restatement

We are given an m x n grid called rooms.

Each cell has one of three values:

We need to fill each empty room with the distance to its nearest gate.

Distance is the number of steps needed to reach a gate by moving only up, down, left, or right.

If an empty room cannot reach any gate, it should remain INF.

The problem uses 2147483647 as INF, and assumes every reachable distance is smaller than that value.

Input and Output

Function shape:

class Solution:
    def wallsAndGates(self, rooms: list[list[int]]) -> None:
        ...

Examples

For:

INF = 2147483647

rooms = [
    [INF, -1,  0, INF],
    [INF, INF, INF, -1],
    [INF, -1, INF, -1],
    [0,   -1, INF, INF],
]

The result should be:

[
    [3, -1, 0, 1],
    [2,  2, 1, -1],
    [1, -1, 2, -1],
    [0, -1, 3, 4],
]

The top-left room gets value 3 because the nearest gate is three steps away:

(0, 0) -> (1, 0) -> (2, 0) -> (3, 0)

The room at (0, 3) gets value 1 because it is next to the gate at (0, 2).

First Thought: BFS From Every Empty Room

A direct solution is to run BFS from each empty room until we find the nearest gate.

For each INF cell:

1. Start a BFS from that room.
2. Search outward level by level.
3. Stop when we reach a gate.
4. Write that distance into the room.

This is correct because BFS finds the shortest path in an unweighted grid.

But it repeats a lot of work.

If there are many empty rooms, each BFS may scan a large part of the grid again.

Problem With Repeated BFS

Let the grid have m rows and n columns.

There are up to m * n empty rooms.

A BFS from one room can also visit up to m * n cells.

So repeated BFS can cost:

O((m * n) * (m * n))

That is too expensive.

We need one BFS that computes all distances together.

Key Insight

Instead of starting BFS from every empty room, start BFS from every gate at the same time.

This is called multi-source BFS.

All gates begin with distance 0.

Then BFS expands outward:

The first time BFS reaches an empty room, it must be through the nearest gate, because BFS expands in increasing distance order.

This fills every reachable room exactly once.

Algorithm

Create a queue.

Scan the whole grid.

Whenever we find a gate:

rooms[r][c] == 0

push its coordinates into the queue.

Then run BFS.

For each cell popped from the queue:

1. Check its four neighbors.
2. Ignore neighbors outside the grid.
3. Ignore walls.
4. Ignore gates or rooms that already have a distance.
5. For each unvisited empty room, set:

rooms[nr][nc] = rooms[r][c] + 1

6. Push that neighbor into the queue.

Because INF means unvisited empty room, we do not need a separate visited array.

Correctness

All gates are inserted into the queue before BFS begins, and each gate has distance 0.

BFS processes cells in increasing distance order. So when an empty room is reached for the first time, the path used to reach it has the smallest possible number of steps from any gate.

The algorithm writes a distance only when the cell is still INF. After that, the room is never updated again.

This is correct because the first written distance is already the shortest distance. Any later path would be at the same distance or longer, since BFS expands level by level.

Walls are never entered, so all paths counted by the algorithm are valid grid paths.

Rooms that cannot be reached from any gate are never visited, so they remain INF.

Therefore, after BFS finishes, every reachable empty room contains its shortest distance to the nearest gate, and every unreachable empty room remains INF.

Complexity

Let:

R = number of rows
C = number of columns

Implementation

from collections import deque

class Solution:
    def wallsAndGates(self, rooms: list[list[int]]) -> None:
        if not rooms or not rooms[0]:
            return

        rows = len(rooms)
        cols = 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))

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

        while queue:
            r, c = queue.popleft()

            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                if nr < 0 or nr >= rows:
                    continue

                if nc < 0 or nc >= cols:
                    continue

                if rooms[nr][nc] != INF:
                    continue

                rooms[nr][nc] = rooms[r][c] + 1
                queue.append((nr, nc))

Code Explanation

We handle an empty grid first:

if not rooms or not rooms[0]:
    return

Then we store the grid size:

rows = len(rooms)
cols = len(rooms[0])

The problem uses this value for empty rooms:

INF = 2147483647

We collect every gate into the queue:

if rooms[r][c] == 0:
    queue.append((r, c))

This is the multi-source part. BFS starts from all gates together.

The four possible moves are:

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

During BFS, we pop one cell:

r, c = queue.popleft()

Then we inspect its neighbors.

If a neighbor is outside the grid, skip it.

If a neighbor is not INF, skip it.

That means we skip walls, gates, and already-filled rooms:

if rooms[nr][nc] != INF:
    continue

For each unvisited empty room, we write the distance:

rooms[nr][nc] = rooms[r][c] + 1

Then we push it into the queue so it can expand to its neighbors.

Testing

def test_walls_and_gates():
    s = Solution()
    INF = 2147483647

    rooms = [
        [INF, -1,  0, INF],
        [INF, INF, INF, -1],
        [INF, -1, INF, -1],
        [0,   -1, INF, INF],
    ]

    s.wallsAndGates(rooms)

    assert rooms == [
        [3, -1, 0, 1],
        [2,  2, 1, -1],
        [1, -1, 2, -1],
        [0, -1, 3, 4],
    ]

    rooms = [[0]]
    s.wallsAndGates(rooms)
    assert rooms == [[0]]

    rooms = [[INF]]
    s.wallsAndGates(rooms)
    assert rooms == [[INF]]

    rooms = [
        [INF, -1],
        [-1,  0],
    ]
    s.wallsAndGates(rooms)
    assert rooms == [
        [INF, -1],
        [-1,  0],
    ]

    print("all tests passed")

test_walls_and_gates()

Test meaning: