Walls and Gates (LeetCode 286)
You're given an m x n floor plan rooms, where every cell holds one of three values: -1 marks a wall you can't walk through, 0 marks a gate, and the sentinel INF (231 - 1, i.e. 2147483647) marks an empty room — you can assume any room that can reach a gate is always closer than that sentinel value.
Update the grid in place so every empty room instead holds the number of steps to the nearest gate, moving one cell at a time in the four compass directions. Any room a gate can never reach should keep its INF value.
Worked Examples
rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]][[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]-1 and gates stay 0.rooms = [[-1]][[-1]]⚖️Formal Constraints & Bounds
m == rooms.lengthn == rooms[i].length1 <= m, n <= 250rooms[i][j]is-1,0, or231 - 1.
Core Insight
Multi-source BFS ensures optimal distance assignment in a single O(R · C) pass.
Real-World Scenario & Production Applications
Emergency evacuation exit routing, fire alarm propagation modeling.
Step-by-Step Execution Trace Table
| Distance Wave | Processing Cells | Updated Neighbor Rooms |
|---|---|---|
| 0 | (0, 2), (3, 0) | Seed initial gates |
| 1 | (0, 3)=1, (1, 2)=1, (2, 0)=1 | Neighbors of gates |
| 2 | (1, 1)=2, (2, 2)=2, (1, 0)=2 | 2 steps from gates |
| 3 | (0, 0)=3, (3, 2)=3 | 3 steps from gates |
| 4 | (3, 3)=4 | Corner reached |
rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]][[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]| Distance Wave | Processing Cells | Updated Neighbor Rooms |
|---|---|---|
| 0 | (0, 2), (3, 0) | Seed initial gates |
| 1 | (0, 3)=1, (1, 2)=1, (2, 0)=1 | Neighbors of gates |
| 2 | (1, 1)=2, (2, 2)=2, (1, 0)=2 | 2 steps from gates |
| 3 | (0, 0)=3, (3, 2)=3 | 3 steps from gates |
| 4 | (3, 3)=4 | Corner reached |
| 1 | queue = deque(all_gates) |
| 2 | while queue: |
| 3 | r, c = queue.popleft() |
| 4 | for each neighbor (nr, nc) in the 4 directions: |
| 5 | if (nr, nc) is inside the grid and rooms[nr][nc] == INF: |
| 6 | rooms[nr][nc] = rooms[r][c] + 1 |
| 7 | queue.append((nr, nc)) |
Conceptual Narrative
Walls and Gates computes distance from every empty room to the nearest gate simultaneously using multi-source breadth-first search.
🧭 Conceptual Foundation & Pattern Intuition
Running individual BFS from every empty room costs where is the number of rooms. Instead, multi-source BFS enqueues ALL gates simultaneously at distance 0 and expands outward concentrically. The first time an empty room is reached, its recorded distance is mathematically guaranteed to be the shortest.
🏟️ The Analogy: Synchronous Wildfire Expansion
Imagine lighting fires at multiple designated fire pits (gates) in a forest at the same exact second. The fire spreads 1 meter per minute in all directions. The minute fire reaches any tree is its exact distance to the nearest fire pit.
🔑 Why It Works
Overwriting empty rooms INF with dist + 1 immediately serves as the visited mark, preventing redundant enqueues.
Single-source BFS TLE: Running separate BFS passes from each empty room takes time; multi-source BFS from all gates simultaneously runs in .
Marking visited on pop instead of push: Waiting to mark rooms visited upon pop causes cells to be enqueued multiple times, blowing up queue memory to .
Overwriting walls (-1) or existing gates (0): Failing to guard
rooms[nr][nc] == 2147483647overwrites obstacles and gates.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Shortest distance from multiple concurrent origins in an unweighted grid.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: first arrival at any empty room is guaranteed to be minimal distance.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Running BFS from each gate separately (O(K · R · C) vs optimal O(R · C)).
Mutating walls or gate cells.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I initialize a queue with all gate coordinates
(r, c)whererooms[r][c] == 0. I run multi-source BFS: whenever exploring an empty room (2147483647), I updaterooms[nr][nc] = rooms[r][c] + 1and enqueue. Runs in O(R · C) time and O(R · C) queue memory."
Complexity & Mathematical Proof
O(M · N)
Look at the execution steps: Multi-source BFS begins at all gates (0) simultaneously and updates INF rooms with their shortest distance in O(1) per room. Total M · N cell visits.
O(M · N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Queue holds active wavefront rooms.
T(M, N) = O(M · N)
Derivation Progression
O(M · N) initial scan
Finds all 0-distance gates.
grid[nr][nc] = grid[r][c] + 1
Sets room distance from nearest gate.
≤ M · N modifications
Each room is finalized on first arrival.
Variable Definitions
Total number of rows in the grid
Total number of columns in the grid
Memory Architecture & Bounds
O(1) Iterative
O(M · N) Queue memory
O(1) In-place grid update
Boundary Best / Worst Cases
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "fill each empty room with distance to nearest gate". Running independent BFS from each gate takes . A Senior SWE applies Multi-Source BFS: enqueue all gates () simultaneously at and expand outward in concentric unit-distance rings.
. Multi-source BFS visits each room at most once in time (ms).
Unreachable rooms remain (INF). Obstacle walls () must not be traversed.
Walls and Gates (LeetCode 286)
You're given an m x n floor plan rooms, where every cell holds one of three values: -1 marks a wall you can't walk through, 0 marks a gate, and the sentinel INF (231 - 1, i.e. 2147483647) marks an empty room — you can assume any room that can reach a gate is always closer than that sentinel value.
Update the grid in place so every empty room instead holds the number of steps to the nearest gate, moving one cell at a time in the four compass directions. Any room a gate can never reach should keep its INF value.
Worked Examples
rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]][[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]-1 and gates stay 0.rooms = [[-1]][[-1]]⚖️Formal Constraints & Bounds
m == rooms.lengthn == rooms[i].length1 <= m, n <= 250rooms[i][j]is-1,0, or231 - 1.
Core Insight
Multi-source BFS ensures optimal distance assignment in a single O(R · C) pass.
Real-World Scenario & Production Applications
Emergency evacuation exit routing, fire alarm propagation modeling.
Step-by-Step Execution Trace Table
| Distance Wave | Processing Cells | Updated Neighbor Rooms |
|---|---|---|
| 0 | (0, 2), (3, 0) | Seed initial gates |
| 1 | (0, 3)=1, (1, 2)=1, (2, 0)=1 | Neighbors of gates |
| 2 | (1, 1)=2, (2, 2)=2, (1, 0)=2 | 2 steps from gates |
| 3 | (0, 0)=3, (3, 2)=3 | 3 steps from gates |
| 4 | (3, 3)=4 | Corner reached |
rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]][[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]| Distance Wave | Processing Cells | Updated Neighbor Rooms |
|---|---|---|
| 0 | (0, 2), (3, 0) | Seed initial gates |
| 1 | (0, 3)=1, (1, 2)=1, (2, 0)=1 | Neighbors of gates |
| 2 | (1, 1)=2, (2, 2)=2, (1, 0)=2 | 2 steps from gates |
| 3 | (0, 0)=3, (3, 2)=3 | 3 steps from gates |
| 4 | (3, 3)=4 | Corner reached |
| 1 | queue = deque(all_gates) |
| 2 | while queue: |
| 3 | r, c = queue.popleft() |
| 4 | for each neighbor (nr, nc) in the 4 directions: |
| 5 | if (nr, nc) is inside the grid and rooms[nr][nc] == INF: |
| 6 | rooms[nr][nc] = rooms[r][c] + 1 |
| 7 | queue.append((nr, nc)) |
Conceptual Narrative
Walls and Gates computes distance from every empty room to the nearest gate simultaneously using multi-source breadth-first search.
🧭 Conceptual Foundation & Pattern Intuition
Running individual BFS from every empty room costs where is the number of rooms. Instead, multi-source BFS enqueues ALL gates simultaneously at distance 0 and expands outward concentrically. The first time an empty room is reached, its recorded distance is mathematically guaranteed to be the shortest.
🏟️ The Analogy: Synchronous Wildfire Expansion
Imagine lighting fires at multiple designated fire pits (gates) in a forest at the same exact second. The fire spreads 1 meter per minute in all directions. The minute fire reaches any tree is its exact distance to the nearest fire pit.
🔑 Why It Works
Overwriting empty rooms INF with dist + 1 immediately serves as the visited mark, preventing redundant enqueues.
Single-source BFS TLE: Running separate BFS passes from each empty room takes time; multi-source BFS from all gates simultaneously runs in .
Marking visited on pop instead of push: Waiting to mark rooms visited upon pop causes cells to be enqueued multiple times, blowing up queue memory to .
Overwriting walls (-1) or existing gates (0): Failing to guard
rooms[nr][nc] == 2147483647overwrites obstacles and gates.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Shortest distance from multiple concurrent origins in an unweighted grid.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: first arrival at any empty room is guaranteed to be minimal distance.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Running BFS from each gate separately (O(K · R · C) vs optimal O(R · C)).
Mutating walls or gate cells.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I initialize a queue with all gate coordinates
(r, c)whererooms[r][c] == 0. I run multi-source BFS: whenever exploring an empty room (2147483647), I updaterooms[nr][nc] = rooms[r][c] + 1and enqueue. Runs in O(R · C) time and O(R · C) queue memory."
Complexity & Mathematical Proof
O(M · N)
Look at the execution steps: Multi-source BFS begins at all gates (0) simultaneously and updates INF rooms with their shortest distance in O(1) per room. Total M · N cell visits.
O(M · N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Queue holds active wavefront rooms.
T(M, N) = O(M · N)
Derivation Progression
O(M · N) initial scan
Finds all 0-distance gates.
grid[nr][nc] = grid[r][c] + 1
Sets room distance from nearest gate.
≤ M · N modifications
Each room is finalized on first arrival.
Variable Definitions
Total number of rows in the grid
Total number of columns in the grid
Memory Architecture & Bounds
O(1) Iterative
O(M · N) Queue memory
O(1) In-place grid update
Boundary Best / Worst Cases
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "fill each empty room with distance to nearest gate". Running independent BFS from each gate takes . A Senior SWE applies Multi-Source BFS: enqueue all gates () simultaneously at and expand outward in concentric unit-distance rings.
. Multi-source BFS visits each room at most once in time (ms).
Unreachable rooms remain (INF). Obstacle walls () must not be traversed.