286. Walls and Gates

286

MediumGraph DFS and BFSBFS from all gates at onceMulti-source BFS distance fill

Walls and Gates

Given an m x n grid of rooms where -1 is a wall, 0 is a gate, and 2147483647 (INF) is an empty room, fill each empty room with the distance to its nearest gate. If no gate can reach a room, leave it as INF. Modify the grid in place.

Open official problem prompt ↗

In plain English

Label every reachable empty room with its shortest walking distance to the nearest gate.

Picture it like this

Imagine every gate releasing water at the same instant; the water floods the hallways one step per second, and each room records the second at which water first arrives.

Example

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
Why: Each empty room is labeled by its shortest 4-directional walking distance to the nearest gate, with walls (-1) blocking paths.

Constraints

m == rooms.lengthn == rooms[i].length1 <= m, n <= 250rooms[i][j] is -1, 0, or 2147483647

Pattern lesson

See the pattern, then code

Multi-source BFS distance fill

↗

Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. Start BFS from every gate at distance 0 at the same time; the first BFS wave to reach an empty room does so along the shortest path, so the wave number is that room's distance.

New words, made simpleKnow these before the algorithm

Gate: A source cell with value 0 from which distances are measured.
Multi-source BFS: BFS started from many sources so the nearest source wins each cell.
In-place fill: Writing distances directly into the grid, using INF as the unvisited marker.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

BFS from each empty room

Rerunning BFS per room is far too slow for a 250x250 grid.

For every empty room, run a BFS to find its closest gate.

Time O((m*n)^2)Space O(m*n)

Best choiceSingle multi-source BFS from all gates

One pass fills every reachable room with its correct nearest distance.

Seed all gates and let the combined wavefront assign the nearest distance to each room.

Time O(m*n)Space O(m*n)

The rule we keep true

Invariant

When a room is first assigned a value it equals its true shortest distance to some gate, because BFS reaches cells in nondecreasing distance order.

Why this is correct

Reasoning

All gates begin at distance 0 in the same queue, so the first wave to touch a room comes from the closest gate; using INF as the unvisited flag guarantees each room is written exactly once with its minimum distance.

The algorithm in three movesSay these aloud before coding

1Enqueue every gate (cell equal to 0)

queue seeded with gates (0,2),(3,0)

2Pop a cell and look at its four neighbors

gate (0,2) fills (0,3)=1

3For any empty room (still INF), set its value to current cell + 1 and enqueue it

wave fills nearest distances

4Continue until the queue is empty; unreached rooms stay INF

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

INF0

-11

INF3

1 · Readscan grid

2 · AskWhich cells are 0?

3 · Update statequeue=[(0,2),(3,0)]

4 · ResultBoth gates enqueued at distance 0

Key takeaway

A row fragment where the gate 0 fills its INF neighbor with distance 1 while the wall -1 blocks flow.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 10-14Seed all gates
Every 0 cell becomes a BFS source at distance 0.
2
Lines 15-21Expand the wavefront
Each INF neighbor is assigned current distance + 1 and enqueued, so rooms are filled shortest-first.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Grid with no gates leaves every room as INF
Rooms fully walled off from any gate stay INF
Grid that is entirely walls or entirely gates
A single-cell grid

Common beginner mistakes

Running BFS from each room instead of from the gates, causing time-limit failures
Treating -1 walls as passable and overwriting them
Overwriting a room's distance on a later, longer path (only fill when the cell is still INF)
Forgetting that unreachable rooms must remain INF, not 0

Check your understanding

Why does seeding all gates at once give each room its nearest gate distance without extra comparison?

PyPython 3 · solution.py

Optimal

1from collections import deque234class Solution:5    def wallsAndGates(self, rooms: list[list[int]]) -> None:6        if not rooms or not rooms[0]:7            return8        INF = 21474836479        rows, cols = len(rooms), len(rooms[0])10        queue = deque()11        for r in range(rows):12            for c in range(cols):13                if rooms[r][c] == 0:14                    queue.append((r, c))15        while queue:16            r, c = queue.popleft()17            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):18                nr, nc = r + dr, c + dc19                if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == INF:20                    rooms[nr][nc] = rooms[r][c] + 121                    queue.append((nr, nc))

Time complexityO(m * n)Optimized

Space complexityO(m * n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

MetaAmazonGoogle

Walls and Gates

Walls and Gates

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Graph DFS and BFS