#286 Walls and Gates
the problem
In plain words
A floor plan is an m × n grid of ints: -1 is a wall, 0 is a gate, and 2147483647 (Integer.MAX_VALUE, call it INF) is an empty room. Fill every empty room, in place, with the number of steps (up, down, left, right) to its nearest gate. Walls can't be crossed. A room that can't reach any gate keeps INF.
in rooms = [[INF,-1,0,INF],[INF,INF,INF,-1],[INF,-1,INF,-1],[0,-1,INF,INF]]
out [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
INF = 2147483647. The top-left room is 3 steps from the gate in the bottom-left corner.
in rooms = [[-1]]
out [[-1]]
Just a wall — nothing to fill.
- 1 ≤ m, n ≤ 250
- rooms[i][j] is -1, 0 or 2147483647
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code right here. Stuck for 20 minutes? Open one hint at a time.
This one is LeetCode Premium. You don't need a subscription: solve it right here. The free alternative linked above is the closest free practice; its label says how close it is.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternMulti-source BFS
Every gate spreads outward at the same speed, so start one BFS from all gates together. The first wave to reach a room comes from its nearest gate — and INF doubles as the "not visited yet" mark.
solutions
From brute force to optimal
Run a separate BFS from each gate and let every room keep the smallest distance it was offered.
- For each gate: BFS with a fresh
seengrid. - At each room reached: rooms[r][c] = min(rooms[r][c], steps).
g gates, each BFS may cover all m·n cells. With gates everywhere, that's O((m·n)²).
A fresh seen grid and queue per BFS.
class Solution { /** One BFS per gate; every room keeps the smallest distance any gate offered. */ public void wallsAndGates(int[][] rooms) { int rows = rooms.length, cols = rooms[0].length; for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (rooms[r][c] == 0) spread(rooms, r, c); } private void spread(int[][] rooms, int sr, int sc) { int rows = rooms.length, cols = rooms[0].length; int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; boolean[][] seen = new boolean[rows][cols]; // fresh for every gate Deque<int[]> queue = new ArrayDeque<>(); queue.offer(new int[] {sr, sc, 0}); seen[sr][sc] = true; while (!queue.isEmpty()) { int[] cur = queue.poll(); for (int[] d : dirs) { int nr = cur[0] + d[0], nc = cur[1] + d[1], steps = cur[2] + 1; if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || seen[nr][nc]) continue; if (rooms[nr][nc] <= 0) continue; // a wall, or another gate seen[nr][nc] = true; rooms[nr][nc] = Math.min(rooms[nr][nc], steps); // keep the nearest gate's distance queue.offer(new int[] {nr, nc, steps}); } } }}Enqueue every gate first. BFS outward; a room is filled only while it still holds INF, so it is filled once — by the nearest gate.
- Enqueue every cell with 0.
- Poll a cell; for each in-bounds neighbour that is INF: set it to this cell's value + 1 and enqueue it.
- Walls (-1), gates (0) and filled rooms are never INF, so they are skipped automatically.
Every room is filled and enqueued at most once; each checks 4 neighbours.
The queue can hold many cells at once (all the gates, to begin with).
class Solution { /** Start from ALL gates at once: the first time BFS reaches a room is from its nearest gate. */ public void wallsAndGates(int[][] rooms) { int rows = rooms.length, cols = rooms[0].length; Deque<int[]> queue = new ArrayDeque<>(); for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (rooms[r][c] == 0) queue.offer(new int[] {r, c}); // every gate is a source int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; while (!queue.isEmpty()) { int[] cell = queue.poll(); for (int[] d : dirs) { int nr = cell[0] + d[0], nc = cell[1] + d[1]; if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue; if (rooms[nr][nc] != Integer.MAX_VALUE) continue; // wall, gate, or already filled rooms[nr][nc] = rooms[cell[0]][cell[1]] + 1; // filling the room = marking it visited queue.offer(new int[] {nr, nc}); } } }}in the room
How to say it in the interview
talk track
- Say: "Distance to the nearest of many sources → multi-source BFS, seeded with every gate."
- Point out that INF is the visited mark: once a room holds a number, it's final.
- Mention why a DFS from each gate is a trap: it keeps revisiting rooms whenever it finds a shorter route — exponential on an open floor.
traps
- DFS from each gate that re-enters a room whenever it finds a shorter distance: correct but explodes on open floors.
- Writing
rooms[nr][nc] + 1instead ofrooms[r][c] + 1(or comparing against 0 instead of INF) — walls and gates get overwritten. - Adding 1 to INF anywhere:
Integer.MAX_VALUE + 1overflows to a negative number.
what they ask next
Follow-ups
Return each room's nearest gate id, not just the distance?
Carry the gate id in the queue entry; a room copies the id of the cell that first reached it.
Some moves cost more than others?
Plain BFS no longer works — use Dijkstra (or 0-1 BFS if costs are only 0 or 1). See the Shortest Paths chapter.
before you submit
Edge cases to test
- No gates at all → every room stays INF.
- Rooms walled off from every gate keep INF.
- A single cell that is a wall, a gate, or an INF room.
- Two gates at both ends of a corridor → the middle rooms take the nearer gate's distance.
practise next
Similar problems
- #54201 MatrixMediumin Graphs
- #994Rotting OrangesMediumin Graphs
- #1730Shortest Path to Get FoodMediumin GraphsLeetCode Premium