NeetCode #566LC-286MediumGraphsNC 150NC 250NC Algo100
← Back to All Problems#566 · #286 · Walls and Gates(墙与门)
📌 Problem Statement & Constraints
You are given an
m x n grid of rooms where -1 is a wall, 0 is a gate, and 2147483647 is an empty room. Fill each empty room with the distance to its nearest gate, or leave it as the sentinel if unreachable. Constraints: 1 <= m, n <= 250.💡 Core Algorithmic Approaches
- This is a multi-source BFS: start from every gate simultaneously.
- The first time a room is reached is via the nearest gate, so its distance is final.
- Only empty rooms (the sentinel value) are enqueued, which naturally skips walls and gates.
- Multi-source BFS is the standard tool for "nearest source" grid problems.
💻 Benchmark Python3 Implementation
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
from collections import deque
if not rooms:
return
m, n = len(rooms), len(rooms[0])
INF = 2147483647
q = deque()
for i in range(m):
for j in range(n):
if rooms[i][j] == 0:
q.append((i, j)) # every gate is a source
while q:
r, c = q.popleft()
for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and rooms[nr][nc] == INF:
rooms[nr][nc] = rooms[r][c] + 1
q.append((nr, nc)) # the first visit is the nearest gate⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n): each room is enqueued at most once.
💾 Space Complexity
O(m * n) for the queue.
⚠️ Interview Pitfalls & Follow-ups
- Running a separate BFS per gate: O(gates * m * n); the multi-source BFS is O(m*n).
- Enqueuing cells with
rooms[nr][nc] != -1: walls and gates must be excluded; testing against the sentinel does both. - Modifying the grid before the BFS completes: the distance is written once, on first visit, which is optimal.
- Returning a value: the signature mutates the grid in place.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.