Problem Overview
LeetCode 286 Walls and Gates gives you an m x n grid initialized with three possible values: -1 for a wall or obstacle, 0 for a gate, and INF (2^31 - 1 = 2147483647) for an empty room. Your task is to fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate from a room, leave it as INF.
Movement is restricted to the four cardinal directions (up, down, left, right). You cannot pass through walls. A room's distance to a gate is the minimum number of steps required to walk from that room to any gate in the grid.
This is a shortest-distance problem on an unweighted grid. Unweighted shortest paths scream BFS — but the naive approach of running BFS from each empty room separately is painfully slow on large grids.
- m == rooms.length, n == rooms[i].length; 1 ≤ m, n ≤ 250
- rooms[i][j] is -1 (wall), 0 (gate), or 2^31 - 1 = INF (empty room)
- Modify the grid in-place; return nothing
- Rooms unreachable from any gate remain as INF
- Movement: 4-directional only (up, down, left, right)
Why BFS from Each Room Is Slow
The naive approach runs a separate BFS from each empty room and stops when it first hits a gate. At first glance this seems fine — each BFS is O(m*n) in the worst case, and with up to m*n empty rooms the total time is O((m*n)^2). For a 250x250 grid that is ~3.9 billion operations — way too slow.
The waste comes from redundancy. Consider two adjacent rooms A and B both far from the same gate G. The BFS from room A explores a huge region including room B's territory. Then BFS from room B re-explores almost the same region. Each room does redundant work that overlaps with its neighbors.
The fix is to invert the perspective: instead of asking "how far is this room from the nearest gate?", ask "how far can the gates reach from all directions at once?" That is the multi-source BFS trick.
Flip the Perspective
BFS from gates outward is the classic multi-source BFS trick that reduces complexity from O((m*n)^2) to O(m*n). Instead of finding the nearest gate from each room (many starting points, many re-explorations), seed all gates into the BFS queue simultaneously and let the wave front fill distances as it expands.
Multi-Source BFS
Multi-source BFS works by treating all gate cells as a single collective starting point. Enqueue every cell with value 0 (a gate) before the BFS begins. Then run standard BFS: dequeue a cell, check its four neighbors, and if a neighbor is an empty room (value INF), set its distance to current distance + 1 and enqueue it.
Because BFS processes cells in order of increasing distance, the first time any room is reached is guaranteed to be via the shortest path from the nearest gate. Once a room's distance is set, it will never be revisited — the INF check ensures this.
The algorithm terminates when the queue is empty, meaning every reachable room has been assigned its shortest distance. Rooms that remain INF were surrounded by walls with no path to any gate.
- 1Scan the grid and enqueue all cells where rooms[r][c] == 0 (gates)
- 2BFS loop: dequeue cell (r, c)
- 3For each of 4 neighbors (nr, nc): check bounds
- 4If rooms[nr][nc] == INF (empty room), set rooms[nr][nc] = rooms[r][c] + 1
- 5Enqueue (nr, nc) — it will now propagate distance to its own neighbors
- 6Repeat until queue is empty; unreachable rooms keep their INF value
Why This Gives Shortest Distance
BFS explores nodes in order of increasing distance from the source. In standard single-source BFS, all nodes at distance d are processed before any node at distance d+1. Multi-source BFS preserves this property: all gates (distance 0) are processed first, then all rooms at distance 1, then distance 2, and so on.
The key guarantee: the first time BFS reaches a room, it is via the shortest path from any gate. If room R is at distance 3 from gate G1 and distance 5 from gate G2, BFS will set rooms[R] = 3 when processing G1's wave at level 3. When G2's wave reaches R at level 5, the INF check fails (rooms[R] is already 3) and R is not re-enqueued.
This is the fundamental correctness property of BFS on unweighted graphs. Multi-source BFS extends it naturally by treating the set of all gates as a virtual super-source at distance 0.
Virtual Super-Source Interpretation
Multi-source BFS is equivalent to adding a virtual node S connected to every gate with an edge of cost 0, then running single-source BFS from S. The BFS wave from S reaches all gates simultaneously at distance 0, then expands outward. The distance from S to any room equals the distance from that room to its nearest gate.
In-Place Modification
The problem asks you to modify the grid in-place. This is convenient: you can use the grid itself to track which rooms have been visited. A room with value INF has not yet been reached; once you set its distance, it will never equal INF again and will not be re-enqueued.
Walls (value -1) are never touched. Gates (value 0) are enqueued initially but never overwritten — their distance is 0 by definition. The condition to enqueue a neighbor is simply rooms[nr][nc] == INF, which handles all three cases correctly without needing a separate visited set.
This in-place approach saves O(m*n) space compared to maintaining a separate boolean visited array. The grid itself becomes the distance map as the algorithm runs.
- 1No separate visited array needed — use rooms[r][c] == INF as the unvisited check
- 2Walls (-1) are never enqueued; the INF check skips them
- 3Gates (0) are enqueued initially; neighbors check rooms[r][c] + 1 = 1 for first ring
- 4Once rooms[nr][nc] is set to a distance, subsequent BFS waves skip it (not INF)
- 5After BFS, rooms with INF value are unreachable from any gate
Code Walkthrough Python and Java
In Python: import deque from collections. INF = 2**31 - 1. Collect all gates into the initial deque. Define DIRS = [(0,1),(0,-1),(1,0),(-1,0)]. BFS loop: pop left, iterate DIRS, check bounds and rooms[nr][nc] == INF, set rooms[nr][nc] = rooms[r][c] + 1, append to queue. Total time O(m*n), space O(m*n) for the queue.
In Java: import LinkedList and Queue. Scan grid to add all gate coordinates to the queue. int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}}. While queue not empty: poll [r,c], iterate dirs, check bounds and rooms[nr][nc] == Integer.MAX_VALUE, set rooms[nr][nc] = rooms[r][c] + 1, offer to queue.
Both implementations are virtually identical in structure — the only differences are syntax and data type names. The core logic is: collect gates, BFS outward, check INF for unvisited rooms, set distance, enqueue.
Check for INF, Not Just Non-Wall
The neighbor check must be rooms[nr][nc] == INF (or Integer.MAX_VALUE in Java), not rooms[nr][nc] != -1. If you check != -1, you will revisit gates (value 0) and rooms already assigned distances, causing incorrect distance values and potential infinite loops. The INF check is what makes in-place visited tracking work correctly.