Skip to content

Volume ITechnology

4.20.7 — Walls and Gates ​

LeetCode 286 · Medium

The problem ​

A grid holds -1 (a wall), 0 (a gate) and INF (an empty room, given as 2^{31}-1). Fill each empty room with the distance to its nearest gate. Rooms that cannot reach any gate stay INF.

INF  -1   0  INF          3  -1   0   1
INF INF INF  -1     →     2   2   1  -1
INF  -1 INF  -1           1  -1   2  -1
  0  -1 INF INF           0  -1   3   4

In plain English, you are given a 2D grid representing a building. -1 cells are walls (impassable). 0 cells are gates (exits). INF (2147483647) cells are empty rooms. For every empty room, you need to replace INF with the length of the shortest path to reach the nearest gate. You can move up, down, left, right. If a room is completely walled off and cannot reach a gate, leave it as INF. The grid is mutated in-place.

The pattern ​

Exactly 4.20.6 Rotting Oranges with different labels. Gates are the rotten oranges, rooms are the fresh ones, and instead of counting rounds you write the round number into the cell.

A picture to hold in mind ​

Imagine being lost in a dark maze with hundreds of rooms, looking for an exit sign. If you start from your room and wander blindly (running a search from every room), you'll waste a lot of time. Instead, imagine someone at every exit gate turns on a super bright flashlight. The light floods down the hallways, bouncing one room at a time. The first time light hits your room, you know the exact shortest distance to the gate because light travels in straight, expanding waves. Multi-source BFS is just "turning on the flashlights at all gates simultaneously."

The brute force, and where it wastes work ​

The naive approach is a BFS/DFS from every single empty room looking for a gate. If you have a massive grid mostly made of empty rooms, and gates are far away, a search from one room might traverse the entire grid (O(N) operations). If you do this for every empty room (O(N) rooms), you get O(N^2) total operations. On a 250x250 grid, N = 62,500, and N^2 \approx 3.9 billion operations. The reversal (searching from the gates instead) processes every cell exactly once, taking only 62,500 operations.

Multi-source BFS gives every room its distance to the nearest gate in a single pass, because BFS expands in rings and the first ring to reach a room came from the closest gate.

The solution ​

python
from collections import deque

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        if not rooms:  # (1)
            return
        rows, cols = len(rooms), len(rooms[0])
        INF = 2147483647  # (2)

        queue = deque()  # (3)
        for r in range(rows):                    # seed every gate
            for c in range(cols):
                if rooms[r][c] == 0:  # (4)
                    queue.append((r, c))

        while queue:  # (5)
            r, c = queue.popleft()  # (6)
            for nr, nc in ((r+1,c), (r-1,c), (r,c+1), (r,c-1)):
                if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == INF:  # (7)
                    rooms[nr][nc] = rooms[r][c] + 1     # (8) one further than here
                    queue.append((nr, nc))
ts
function wallsAndGates(rooms: number[][]): void {
  if (!rooms.length) return;  // (1)
  const rows = rooms.length, cols = rooms[0].length;
  const INF = 2147483647;  // (2)

  const queue: Array<[number, number]> = [];  // (3)
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (rooms[r][c] === 0) queue.push([r, c]);  // (4)

  let head = 0;                                  // index instead of shift()
  while (head < queue.length) {  // (5)
    const [r, c] = queue[head++];  // (6)
    for (const [nr, nc] of [[r+1,c],[r-1,c],[r,c+1],[r,c-1]] as [number,number][]) {
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && rooms[nr][nc] === INF) {  // (7)
        rooms[nr][nc] = rooms[r][c] + 1;  // (8)
        queue.push([nr, nc]);
      }
    }
  }
}

This version is even simpler than Rotting Oranges, because the distance is stored in the grid rather than counted, so there is no need to process the queue level by level. Each cell's value is its parent's value plus one, and that is automatically the ring number.

rooms[nr][nc] == INF does three jobs at once. It rejects walls (-1), rejects gates (0), and rejects rooms already filled in — because a filled room no longer holds INF. That single comparison is the visited check.

Writing the distance is the visited mark, and it happens on enqueue. A room reached by two gates in the same ring would otherwise be queued twice; the first write blocks the second.

Why the first arrival is the nearest gate. BFS processes cells in non-decreasing distance order. A room is written when it is first reached, and any later route to it is at least as long, so no update is ever needed. That is the property that makes BFS the right tool and DFS the wrong one.

In TypeScript, use a head index rather than Array.shift(). shift() is O(n) in principle, which would turn a linear algorithm quadratic on a large grid.

Line by line ​

(1) An empty map needs nothing.

(2) The value the problem uses for "an empty room not yet given a distance". It is the largest 32-bit whole number, 2^{31} - 1.

(3) A queue for a breadth-first search.

(4) Every gate goes into the queue at the start. All gates spread outward at the same time. A room is then reached first by its nearest gate, because breadth-first search reaches everything one step away before anything two steps away.

(5) Keep going until no room is left to spread from.

(6) Take the next cell. In TypeScript, the queue is a plain array with a head position, because shift() on a JavaScript array is slow.

(7) A neighbour on the map that is still an unvisited empty room. Walls are −1 and gates are 0, so neither equals INF, and both are skipped.

(8) Its distance is one more than this cell's. Writing the distance also marks the room as visited, so it is never given a second, larger distance. Then it joins the queue.

Trace ​

Consider a 1D grid [0, INF, INF, 0]

StepActionQueueGrid State
1Initial scan seeds gates.[(0,0), (0,3)][0, INF, INF, 0]
2Pop (0,0). Neighbors: (0,1).[(0,3)]...
3grid[0][1] is INF. Set to 0 + 1 = 1. Enqueue (0,1).[(0,3), (0,1)][0, 1, INF, 0]
4Pop (0,3). Neighbors: (0,2).[(0,1)]...
5grid[0][2] is INF. Set to 0 + 1 = 1. Enqueue (0,2).[(0,1), (0,2)][0, 1, 1, 0]
6Pop (0,1). Neighbors: (0,0), (0,2). Both are != INF.[(0,2)][0, 1, 1, 0]
7Pop (0,2). Neighbors: (0,1), (0,3). Both are != INF.[][0, 1, 1, 0]

Edge cases ​

  • No gates. Nothing enters the queue, and every room stays at INF.
  • A room walled off from every gate. It is never reached, so it stays at INF, as the problem expects.
  • Several gates. Each room gets the distance to the nearest one, because all gates start together.

Complexity ​

O(rows \times cols) time — each cell is written once and enqueued once. To break it down: finding the initial gates takes a single pass over the entire grid, costing O(rows \times cols). During the BFS phase, a cell is pushed to the queue only if its value is exactly INF. When it is pushed, its value is immediately overwritten to a number. Therefore, no cell is ever pushed to the queue more than once. The work inside the while loop is exactly proportional to the number of cells enqueued, making the whole BFS phase O(rows \times cols).

O(rows \times cols) space for the queue. In the absolute worst case, the perimeter of the expanding wave from all gates could equal the total number of cells in the grid, bounding the maximum size of the queue.

Compare with the per-room search at O((rows \times cols)^2).

Where this goes next ​

The same six lines, relabelled:

problemsourceswhat is written
Walls and Gatesgatesdistance to the nearest gate
01 Matrixevery 0distance to the nearest zero
Rotting Orangesrotten orangesthe round number, returned as a total
As Far from Land as Possibleland cellsthe maximum distance reached
Map of Highest Peakwater cellsheight, since the constraint is the same as distance

Learn one of these properly and you have all five. The only differences are what seeds the queue and what you do with the answer.

What the interviewer will push on ​

"Why not BFS from each room?" O((rows \times cols)^2) against O(rows \times cols). Say both numbers.

"Why does the first arrival give the shortest distance?" BFS visits cells in non-decreasing distance order, so a later route can never be shorter.

"Where is your visited check?" The == INF test, which also handles walls and gates.

"What if edges had different costs?" BFS's guarantee breaks and you need Dijkstra with a priority queue. 4.21.

"What if there were no gates?" The queue starts empty, nothing happens, and every room stays INF — correct, with no special case.

One thing to volunteer: say that the == INF comparison is doing three checks at once. Noticing where a single condition covers several cases is the kind of small observation that makes code both shorter and obviously correct.

Next: 4.20.8 Course Schedule — leaving grids behind for dependencies, cycles, and topological order.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet