LeetCode 286 · Medium · Graphs

Walls and Gates

A grid holds walls (-1), gates (0) and empty rooms (INF). Fill every room, in place, with the number of steps to its nearest gate, moving up, down, left or right. A room no gate can reach stays INF.

O(m·n)time
O(m·n)space
BFS from every gatelevel = distance

rows separated by ; · cells -1, 0 or INF (2147483647 works) separated by spaces · 1–7 rows × 1–8 columns

Queue front at the left · blue = this level, green = next level

int[][] rooms;boolean[][] visit;Deque<int[]> q = new ArrayDeque<>();public void wallsAndGates(int[][] rooms) { this.rooms = rooms; int rows = rooms.length; int cols = rooms[0].length; visit = new boolean[rows][cols]; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { if (rooms[r][c] == 0) { // every gate starts the BFS q.offer(new int[]{r, c}); visit[r][c] = true; } } } int dist = 0; while (!q.isEmpty()) { int size = q.size(); for (int i = 0; i < size; i++) { int[] cell = q.poll(); int r = cell[0]; int c = cell[1]; rooms[r][c] = dist; addRoom(r + 1, c); addRoom(r - 1, c); addRoom(r, c + 1); addRoom(r, c - 1); } dist++; }}private void addRoom(int r, int c) { if (r < 0 || c < 0 || r == rooms.length || c == rooms[0].length || visit[r][c] || rooms[r][c] == -1) { return; } visit[r][c] = true; q.offer(new int[]{r, c});}
dist
0
(r, c)
—
q.size()
0
visited cells
0

Why it works

  1. Brute force runs a BFS from every empty room until it meets a gate: O((m·n)²). Running one BFS from each gate separately is no better.
  2. Start from all gates at once. With every gate in the queue at level 0, the BFS levels grow outward in lockstep, so the first time a room is reached it is by its nearest gate. Level number = distance.
  3. O(m·n) time and space: visit lets each room into the queue once, and each popped room makes 4 addRoom calls.
  4. Pitfall: mark a room in visit when you enqueue it, not when you pop it; otherwise two neighbours on the same level both enqueue it. A wall never enters the queue, and a room boxed in by walls keeps INF (Integer.MAX_VALUE, 2147483647).
  5. Related: Rotting Oranges (994) is the same multi-source BFS, counting levels instead of writing them; 01 Matrix (542) is this problem with 0s as gates.