Graphs crash course ↗ · 98

286. Walls and Gates

Fill each empty room with the distance to its nearest gate. The trick: instead of running a BFS from every room (slow), launch a single multi-source BFS simultaneously from every gate, so the first time a BFS wave reaches a room it is guaranteed to carry the shortest distance.

● MediumMulti-source BFSMatrix BFSTypeScript

PROBLEM What we're solving

You have an m × n grid where each cell is one of three things: a wall (-1), a gate (0), or an empty room (INF = 2147483647). Fill every empty room with the number of steps to its nearest gate. Rooms with no path to any gate stay at INF. Modify the grid in-place.

Concrete example — 4×4 grid:

Input:
INF  -1   0  INF
INF INF INF  -1
INF  -1  INF  -1
  0  -1  INF INF

Output:
  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

The gate at [0][2] fills its neighbours first; the gate at [3][0] fills the bottom-left corner. Every room gets the minimum of its distances to both gates.

KEY IDEA Run BFS from all gates at once, not from each room

Insight →BFS explores cells layer by layer. If you start from every gate simultaneously, each layer is "one step farther from the nearest gate." The first time BFS reaches any room, it has taken the shortest possible path — no room is ever re-visited. One pass fills the entire grid in O(m · n).

RECIPE Multi-source BFS, step by step

0 · Scan for gates. Walk every cell; push (r, c) onto the queue for each cell with value 0. This seeds distance-0 for all gates at once.
1 · Standard BFS loop. Use a plain array + a head pointer as a queue. Dequeue (r, c).
2 · Expand 4 neighbours. For each neighbour (nr, nc) that is in bounds and equals INF, set rooms[nr][nc] = rooms[r][c] + 1 and enqueue it.
3 · Skip non-INF cells. Walls (-1) and already-settled rooms are both non-INF, so the single check rooms[nr][nc] !== INF handles both. No visited set needed.
4 · Repeat until queue is empty. Every reachable room is settled exactly once. Unreachable rooms keep INF.

Classic confusion → A common mistake is running a separate BFS from every INF room and taking the minimum — that is O((m·n)²) in the worst case. Multi-source BFS avoids it by flipping the direction: push the gates, let the rooms come to you. The guard rooms[nr][nc] !== INFalso doubles as the "visited" check, so you do not need a separate boolean matrix.

COST Complexity & alternatives

BFS from each room

O((mn)²)

One full BFS per INF cell in the worst case.

Multi-source BFS

O(mn)

Every cell enqueued and dequeued at most once.

Space is also O(mn) for the queue in the worst case (all cells reachable, all gates in one corner). The input matrix itself is mutated in-place, so no extra grid copy is needed.

Pattern transfer →Multi-source BFS is the right tool for any "minimum distance from a set of sources" problem: 01 Matrix (distance to nearest 0), Rotting Oranges (time for all oranges to rot), and Pacific Atlantic Water Flow (start from both coastlines). Whenever the problem asks for the nearest member of a set, seed the queue with the whole set.

RUN IT Multi-source BFS from every gate simultaneously

Grid

step 0 / 22

STARTGrid has 4×4 cells. Walls = W, gates = 0, rooms = ∞. We seed the BFS queue with every gate.

1▶function wallsAndGates(rooms: number[][]): void {
2▶  const INF = 2147483647;
3▶  const rows = rooms.length;
4▶  const cols = rows > 0 ? rooms[0].length : 0;
5▶  const queue: [number, number][] = [];
6 
7  // Seed: enqueue every gate (distance 0)
8  for (let r = 0; r < rows; r++) {
9    for (let c = 0; c < cols; c++) {
10      if (rooms[r][c] === 0) queue.push([r, c]);
11    }
12  }
13 
14  // BFS: each wave is one step farther from the nearest gate
15  const DIRS: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];
16  let head = 0;
17  while (head < queue.length) {
18    const [r, c] = queue[head++];
19    for (const [dr, dc] of DIRS) {
20      const nr = r + dr, nc = c + dc;
21      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
22      if (rooms[nr][nc] !== INF) continue;   // wall or already settled
23      rooms[nr][nc] = rooms[r][c] + 1;       // BFS guarantees shortest
24      queue.push([nr, nc]);
25    }
26  }
27}

∞

State
head: 0
queue size: 0

source / dequeuedjust filledalready settled

slowfast

TYPESCRIPT The solution, annotated

wallsAndGates.ts
function wallsAndGates(rooms: number[][]): void {
  const INF = 2147483647;
  const rows = rooms.length;
  const cols = rows > 0 ? rooms[0].length : 0;
  const queue: [number, number][] = [];

  // Seed: enqueue every gate (distance 0)
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (rooms[r][c] === 0) queue.push([r, c]);
    }
  }

  // BFS: each wave is one step farther from the nearest gate
  const DIRS: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];
  let head = 0;
  while (head < queue.length) {
    const [r, c] = queue[head++];
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (rooms[nr][nc] !== INF) continue;   // wall or already settled
      rooms[nr][nc] = rooms[r][c] + 1;       // BFS guarantees shortest
      queue.push([nr, nc]);
    }
  }
}

Reading it block by block

Lines 6–10 — seed the queue with every gate. We scan the grid once and enqueue all cells equal to 0. This is the multi-source seed: BFS will now propagate outward from all gates simultaneously, exactly as if they all fired at the same clock tick.

Lines 13–14 — queue setup. Using a plain array with a head pointer avoids the O(n) cost of shift(). The loop runs until every reachable cell has been settled.

Lines 15–21 — expand neighbours. For each dequeued cell (r, c) we check all four directions. The guard rooms[nr][nc] !== INF skips walls (-1) and already-filled rooms in a single comparison — no separate visited set needed. When we write rooms[nr][nc] = rooms[r][c] + 1, BFS distance guarantees this is the shortest path.

After the loop. Every reachable room holds its exact minimum distance. Unreachable rooms (walled off from all gates) still hold INF = 2147483647. No second pass is required.

Complexity → Time: O(m · n) — each cell is enqueued and dequeued at most once. Space: O(m · n) for the queue (at most every cell). The grid is modified in-place; no extra matrix needed.

INTERVIEWFollow-ups they'll ask

"What if there are no gates?" The queue starts empty, the loop never runs, and every room stays INF. Correct by default — no special case needed.
"Can you do it with DFS?" Yes, but DFS does not guarantee shortest path — you would have to re-visit cells when a shorter path is found, making it worse in general. BFS is the right tool here.
"Return distances instead of modifying in place?" Allocate a new matrix pre-filled with INF, run the same BFS writing into it, and return it. Same complexity.
"What if the grid is huge (offline / disk-backed)?" You can process level by level and only keep the current and next frontier in memory, reducing queue peak to O(perimeter) rather than O(mn).
"Generalize to 3D?" Add the third axis and six directions. The algorithm is identical; just extend the bounds checks and DIRS array.

OPTIMAL Multi-source BFS

wallsAndGates.ts
function wallsAndGates(rooms: number[][]): void {
  const INF = 2147483647;
  const rows = rooms.length;
  const cols = rows > 0 ? rooms[0].length : 0;
  const queue: [number, number][] = [];

  // Seed: enqueue every gate (distance 0)
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (rooms[r][c] === 0) queue.push([r, c]);
    }
  }

  // BFS: each wave is one step farther from the nearest gate
  const DIRS: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];
  let head = 0;
  while (head < queue.length) {
    const [r, c] = queue[head++];
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (rooms[nr][nc] !== INF) continue;   // wall or already settled
      rooms[nr][nc] = rooms[r][c] + 1;       // BFS guarantees shortest
      queue.push([nr, nc]);
    }
  }
}

ALT 1 Brute force — separate BFS from every empty room

O((m·n)²) time · O(m·n) space

Instead of one wave from all the gates, run an independent BFS outward from each empty room until it reaches the nearest gate, writing that distance back into the cell.

approach-2.ts
function wallsAndGates(rooms: number[][]): void {
  const INF = 2147483647;
  const rows = rooms.length;
  const cols = rows > 0 ? rooms[0].length : 0;
  const DIRS: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];

  // Shortest distance from (sr, sc) to any gate, or INF if unreachable.
  function nearestGate(sr: number, sc: number): number {
    const dist: number[][] = Array.from({ length: rows }, () =>
      new Array<number>(cols).fill(-1),
    );
    dist[sr][sc] = 0;
    const queue: [number, number][] = [[sr, sc]];
    let head = 0;
    while (head < queue.length) {
      const [r, c] = queue[head++];
      if (rooms[r][c] === 0) return dist[r][c]; // hit a gate
      for (const [dr, dc] of DIRS) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
        if (rooms[nr][nc] === -1) continue;       // wall
        if (dist[nr][nc] !== -1) continue;        // already visited
        dist[nr][nc] = dist[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
    return INF;
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (rooms[r][c] === INF) {
        rooms[r][c] = nearestGate(r, c);
      }
    }
  }
}

Note → Each empty room launches its own full board traversal, so the total work is roughly the number of cells squared — O((m·n)²). The multi-source BFS flips it around: seed the queue with all gates at distance 0 and expand once, so every cell is settled exactly once in O(m·n).

MNEMONIC The one-liner

"Push every gate at time zero — the BFS wave carries the clock. First touch is shortest touch."

TRIGGERS When you see _ → reach for _

"fill each room with distance to nearest gate/source"	multi-source BFS
minimum distance from a set (not a single node)	seed queue with the whole set
rooms[nr][nc] !== INF as visited check	overwrite with distance; wall = -1 also blocked
"rotting oranges / 01 matrix / Pacific Atlantic"	same multi-source BFS template

SKELETON The reusable shape

skeleton.ts
const INF = 2147483647;
const queue: [number, number][] = [];
// 1. seed: every gate
for each cell if rooms[r][c] === 0: queue.push([r,c]);

// 2. BFS wave
let head = 0;
while (head < queue.length) {
  const [r, c] = queue[head++];
  for (const [dr,dc] of DIRS) {
    if (in-bounds && rooms[nr][nc] === INF) {
      rooms[nr][nc] = rooms[r][c] + 1;
      queue.push([nr, nc]);
    }
  }
}

FLASHCARDS Tap to flip

Why start BFS from gates, not from rooms?

Starting from every gate simultaneously fills all rooms in one O(mn) pass. Starting from each room separately is O((mn)²).

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the time complexity of the multi-source BFS approach?

QUESTION 02

The guard rooms[nr][nc] !== INF serves which two purposes at once?

QUESTION 03

After running on the 4×4 example, what value fills cell [0][3] (row 0, col 3)?

QUESTION 04

What happens if you run a single-source BFS from each INF room instead?

QUESTION 05

What should the initial queue contain at the start of the BFS?

QUESTION 06

After the BFS, which cells retain their original INF value?

QUESTION 07

Why is a separate visited boolean matrix unnecessary in this implementation?

QUESTION 08

#286 · Walls and GatesMulti-source BFS from every gate (cell value 0) at once, filling each INF cell with its shortest BFS distance. Each cell is processed at most once for O(m×n) total.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Run BFS from all gates at once, not from each room

RECIPE Multi-source BFS, step by step

COST Complexity & alternatives

RUN IT Multi-source BFS from every gate simultaneously

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Multi-source BFS

ALT 1 Brute force — separate BFS from every empty room

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _