Walls and Gates

Table of Contents +

Walls and Gates is the sister of Rotting Oranges. Both spread from many starting points at once. Here we fill each empty room with the distance to its nearest gate. The same multi source BFS pattern solves it in one clean pass.

🎯 The Problem

You fill every empty room with the number of steps to its nearest gate.

The grid holds three kinds of cells. A -1 is a wall you cannot pass. A 0 is a gate. A large number, treated as infinity, is an empty room.
For every empty room, fill in the distance to its nearest gate.
Distance means the number of steps, moving up, down, left, or right. You cannot pass through walls.
If a room cannot reach any gate, leave it as infinity.

Here is a small grid. We write INF for the large empty room value.

Input grid (-1 wall, 0 gate, INF empty):
   INF  -1    0   INF
   INF  INF  INF   -1
   INF  -1   INF   -1
    0   -1   INF  INF

After filling each room with steps to the nearest gate:
    3   -1    0    1
    2    2    1   -1
    1   -1    2   -1
    0   -1    3    4

Each empty room gets the shortest number of steps to any gate. Walls stay -1. Gates stay 0.

Here is the start. Two gates sit in the grid. The rooms around them will be filled outward.

🐢 Approach 1: Search From Each Room (Brute Force)

We handle each empty room on its own.

The idea:

Stand in an empty room. Start a fresh search from that room to find the closest gate.
Do this for every empty room.

How it works:

Each search crawls outward until it hits the first gate.
Record that distance in the room.

Why it is weak:

You launch a brand new search from each room.
Each search can crawl over much of the grid.
Many rooms share the same paths to the same gate, so the same work repeats.

Here is the BFS-from-each-room code:

from collections import deque
def walls_and_gates(rooms):
    INF = 2147483647
    rows, cols = len(rooms), len(rooms[0])
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == INF:
                q, seen = deque([(r, c, 0)]), {(r, c)}
                while q:
                    x, y, d = q.popleft()
                    if rooms[x][y] == 0:
                        rooms[r][c] = d; break
                    for nx, ny in ((x+1,y),(x-1,y),(x,y+1),(x,y-1)):
                        if 0 <= nx < rows and 0 <= ny < cols and rooms[nx][ny] != -1 and (nx, ny) not in seen:
                            seen.add((nx, ny)); q.append((nx, ny, d + 1))

⚡ Approach 2: Multi Source BFS From All Gates (Best)

The idea in one line: spread out from all gates at once, so the first time a room is reached is its nearest gate distance.

The idea:

Do not start from each room. Start from the gates, and from all gates at the same time.
This is multi source BFS. BFS spreads in rings using a queue.
A queue is a line where you add to the back and remove from the front. Multi source means load every gate into the queue before you begin.

How it works:

Put every gate position in the queue.
Pull a cell. Look at its four neighbors.
A neighbor counts only if it is an empty room still holding infinity.
Set that room to the current cell value plus one, then add it to the queue.
Because you only fill rooms still at infinity, each room is filled once, by the nearest gate.

Why it is fast:

BFS spreads one ring per step, so the first time it reaches a room it came by the shortest path.
No separate distance counter. The distance lives in the grid as the parent value plus one.
Walls are skipped, because they are not empty rooms.

Here is the BFS filling rooms ring by ring out from the gates.

Steps to Solve

Put every gate position into a queue.
While the queue is not empty, take one cell from the front.
Look at its four neighbors. Up, down, left, right.
A neighbor counts only if it is inside the grid and still an empty room holding infinity.
Set that room to the current cell value plus one, then add it to the queue.
When the queue is empty, every reachable room holds its distance to the nearest gate.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses a deque from the collections module and a large INF value.

from collections import deque

INF = 2147483647
grid = [
    [INF, -1, 0, INF],
    [INF, INF, INF, -1],
    [INF, -1, INF, -1],
    [0, -1, INF, INF],
]
R, C = len(grid), len(grid[0])

queue = deque()
for i in range(R):
    for j in range(C):
        if grid[i][j] == 0:       # every gate is a starting source
            queue.append((i, j))

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 < R and 0 <= nc < C and grid[nr][nc] == INF:
            grid[nr][nc] = grid[r][c] + 1   # one step from this cell
            queue.append((nr, nc))

for row in grid:
    print(" ".join("INF" if v == INF else str(v) for v in row))

The output of the above code will be:

Now let us walk through the Python version line by line. We set INF to a very large number. That stands for an empty room with no distance yet. Then the first double loop scans the grid and puts every gate position, every cell equal to 0, into the queue. This is the multi source start. All gates go in together.

The while queue loop runs until the queue is empty. The line r, c = queue.popleft() pulls the cell at the front. Because BFS pulls from the front and adds to the back, cells come out in order of distance. The nearest cells first.

The neighbor check 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == INF does the filtering. It keeps us inside the grid. And the == INF test is the key. It only lets through a cell that is still an unfilled empty room. A wall is -1, so it fails. A gate is 0, so it fails. A room already filled holds a small number, so it fails too. This means each room is filled exactly once.

The fill line grid[nr][nc] = grid[r][c] + 1 writes the distance straight into the grid. The new room is one step further than the cell we came from. Since BFS reaches each room along the shortest path first, this value is the distance to the nearest gate. Then we add the room to the queue so it can spread further.

When the queue empties, every room that could reach a gate holds its shortest distance. Any room still showing INF was sealed off by walls and could never reach a gate.

⏱️ Time and Space Complexity

We fill each room once and add it to the queue once. So the time is O(n), where n is the number of cells. The queue can hold many cells at once, so the space is O(n).

Approach	Time Complexity	Space Complexity
Search from each room (brute force)	O(n²)	O(n)
Multi source BFS from all gates	O(n)	O(n)

Tip

Notice we never keep a separate distance counter. The distance lives in the grid. Each filled room is the parent value plus one. Because BFS reaches each room by the shortest path first, that value is the nearest gate distance.

🧩 Key Takeaways

✅ Start BFS from all gates at once, not from each room. This is multi source BFS.
✅ BFS reaches each room by the shortest path first, so the first fill is the nearest gate distance.
✅ Only fill rooms still holding infinity, so each room is filled exactly once.
✅ The distance lives in the grid itself, as the parent value plus one.
✅ The whole fill runs in O(n) time, where n is the number of cells.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Rotting Oranges
Pacific Atlantic Water Flow

Previous Rotting Oranges Next Course Schedule II

Walls and Gates

Follow Us

Follow Us