Walls and Gates
Explanation & Solution
Description
You are given an m x n grid rooms initialized with these three possible values:
- -1 — A wall or an obstacle.
- 0 — A gate.
- 2147483647 (INF) — An empty room.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, leave the value as 2147483647.
Examples
Example 1
Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
Explanation: The gate at (0,2) fills the top-right area, and the gate at (3,0) fills the bottom-left area. Each empty room gets the shortest distance to any gate via BFS.
Example 2
Input: rooms = [[2147483647,-1],[0,-1]]
Output: [[1,-1],[0,-1]]
Explanation: The only gate is at (1,0). The empty room at (0,0) is 1 step away. The rooms at (0,1) and (1,1) are walls.
Example 3
Input: rooms = [[0,2147483647,2147483647],[2147483647,2147483647,2147483647],[2147483647,2147483647,0]]
Output: [[0,1,2],[1,2,1],[2,1,0]]
Explanation: Two gates at opposite corners. Each room gets filled with the distance to the closer gate.
Constraints
m == rooms.lengthn == rooms[i].length1 <= m, n <= 250rooms[i][j]is-1,0, or2147483647
Approach
Graphs pattern
1. Identify All Gates
- Scan the entire grid for cells with value 0 (gates).
- Add every gate position to a queue. These are the BFS starting points.
2. Initialize Multi-Source BFS
- Instead of running BFS from each gate separately, we start BFS from all gates at once.
- Every gate begins at distance 0, already set in the grid.
3. Process the Queue
- Dequeue a cell and explore its 4 neighbors (up, down, left, right).
- If a neighbor is an empty room (value 2147483647), update its distance to
current cell distance + 1. - Enqueue the neighbor so its own neighbors get processed in turn.
- Skip walls (-1) and already-visited rooms (value < 2147483647).
4. Termination
- BFS naturally terminates when all reachable empty rooms have been filled.
- Rooms that are unreachable from any gate remain 2147483647.
Key Insight
Multi-source BFS processes all gates simultaneously, guaranteeing that each empty room is reached by the closest gate first. This avoids redundant work compared to running separate BFS from each gate, achieving O(m × n) time complexity in a single pass.
Visualization
Press play to start multi-source bfs