⚡Flashcard Drill➔
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

  1. This is a multi-source BFS: start from every gate simultaneously.
  2. The first time a room is reached is via the nearest gate, so its distance is final.
  3. Only empty rooms (the sentinel value) are enqueued, which naturally skips walls and gates.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems