286. Walls and Gates

At a Glance

Topic: graphs
Pattern: BFS (multi-source shortest path on grid)
Difficulty: Medium
Companies: Google, Meta, Amazon, Microsoft, Bloomberg
Frequency: High
LeetCode: 286

Problem (one-liner)

Grid: -1 wall, 0 gate, INF empty room. Fill each empty room with shortest Manhattan distance to any gate (in-place).

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

Shortest steps on unweighted grid — BFS
Many targets — multi-source BFS from all gates at once

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Per cell BFS — O(n^2 m^2) — too slow.
Optimal — one multi-source BFS — O(nm).

Optimal Solution

Go

func wallsAndGates(rooms [][]int) {
	if len(rooms) == 0 {
		return
	}
	rows := len(rooms)
	cols := len(rooms[0])
	const empty = 2147483647
	queue := make([][2]int, 0)
	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			if rooms[row][col] == 0 {
				queue = append(queue, [2]int{row, col})
			}
		}
	}
	directions := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	head := 0
	for head < len(queue) {
		cell := queue[head]
		head++
		for _, delta := range directions {
			nextRow := cell[0] + delta[0]
			nextCol := cell[1] + delta[1]
			if nextRow < 0 || nextCol < 0 || nextRow >= rows || nextCol >= cols {
				continue
			}
			if rooms[nextRow][nextCol] != empty {
				continue
			}
			rooms[nextRow][nextCol] = rooms[cell[0]][cell[1]] + 1
			queue = append(queue, [2]int{nextRow, nextCol})
		}
	}
}

JavaScript

const EMPTY = 2147483647;

function wallsAndGates(rooms) {
  if (rooms.length === 0) {
    return;
  }
  const rows = rooms.length;
  const cols = rooms[0].length;
  const queue = [];
  for (let row = 0; row < rows; row += 1) {
    for (let col = 0; col < cols; col += 1) {
      if (rooms[row][col] === 0) {
        queue.push([row, col]);
      }
    }
  }
  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  let head = 0;
  while (head < queue.length) {
    const cell = queue[head];
    head += 1;
    for (const [deltaRow, deltaCol] of directions) {
      const nextRow = cell[0] + deltaRow;
      const nextCol = cell[1] + deltaCol;
      if (nextRow < 0 || nextCol < 0 || nextRow >= rows || nextCol >= cols) {
        continue;
      }
      if (rooms[nextRow][nextCol] !== EMPTY) {
        continue;
      }
      rooms[nextRow][nextCol] = rooms[cell[0]][cell[1]] + 1;
      queue.push([nextRow, nextCol]);
    }
  }
}