Walls and Gates
Understanding the Problem
We have a 2D grid where some cells are walls (-1), some are gates (0), and the rest are empty rooms (INF). Our job is to update every empty room cell with the shortest distance to the nearest gate. Movement is only allowed in four directions (up, down, left, right), and we cannot pass through walls.
The word "nearest" is what drives the solution. Each empty room needs the minimum distance across all gates, not the distance to one specific gate. One option is to start from each empty room and search outward for the closest gate. The other is to start from the gates and search outward toward the rooms. Starting from the gates turns out to be far cheaper, because a single search from all gates at once fills the entire grid.
That single search is a multi-source BFS. We put all gates into the queue at the start and expand outward from all of them at the same time. Because BFS visits cells in increasing order of distance, the first time it reaches an empty room, the distance recorded is the shortest distance from any gate.
Key Constraints:
1 <= m, n <= 250→ The grid has up to 62,500 cells. A per-room search runs a separate BFS for each of those cells, which is O((m n)^2) in the worst case, around 4 billion operations. A single multi-source pass is O(m n) and stays well within limits.rooms[i][j]is-1,0, or2147483647→ Walls, gates, and empty rooms are the only three values, so the empty-room marker (INF) can double as an "unvisited" flag during BFS.
Approach 1: BFS from Each Empty Room
Intuition
Treat each empty room as an independent shortest-path problem. For every cell that contains INF, run a BFS outward until it hits a gate, and record the number of steps it took.
BFS on an unweighted grid expands one distance level at a time, so the first gate reached from a given room is the closest one to that room. That distance is the answer for that room.
Algorithm
- Iterate through every cell in the grid.
- If the cell is an empty room (value is INF), run a BFS starting from that cell.
- In the BFS, explore neighbors in all four directions (up, down, left, right).
- Skip walls (-1) and already-visited cells.
- The first time we encounter a gate (value 0), that BFS distance is the answer for this room.
- Update the room's value with the distance found.
Example Walkthrough
Code
- Time Complexity: O((m n)^2). In the worst case, every cell is an empty room, and each BFS visits the entire grid. That gives us O(m n) rooms, each taking O(m * n) BFS work.
- Space Complexity: O(m n). Each BFS uses a visited array and a queue, both of which can hold up to O(m n) cells.
This approach is correct but runs a full BFS for every empty room, and adjacent rooms re-explore almost the same cells each time. The next approach reverses the direction: it searches outward from the gates and fills the whole grid in one pass.
Approach 2: Multi-Source BFS from All Gates
Intuition
Instead of asking "for each room, what is the closest gate?", flip the question to "from all gates at once, how far is each room?" Adding every gate to the BFS queue at distance 0 and expanding outward fills the entire grid in a single pass.
A multi-source BFS is one BFS seeded with many starting cells. All gates begin at distance 0. The wavefront then advances one step at a time across the whole grid together. The first time the wavefront reaches a room, that room is recorded at the current distance and never touched again.
Seeding the queue with all gates is equivalent to adding one virtual super-source connected to every gate by a zero-cost edge, then running ordinary BFS from that single source. Ordinary BFS labels each cell with its shortest distance from the source, so each room ends up labeled with its distance to the nearest gate. The first arrival is final: once a room is set, its value is no longer INF, and the rooms[r][c] != INF check blocks any later, longer path from overwriting it.
No separate visited array is needed. A room still holding INF has not been reached; any other value (a wall at -1, a gate at 0, or an assigned distance) is skipped by the same check.
Algorithm
- Create a queue and add the position of every gate (cells with value 0) to it.
- Run BFS. For each cell dequeued, explore its four neighbors.
- For each neighbor that is an empty room (value is still INF), update its distance to
current cell's distance + 1and add it to the queue. - Skip walls (-1) and cells that have already been updated (value is no longer INF).
- When the queue is empty, every reachable empty room has been filled with its shortest distance to any gate.
Example Walkthrough
Code
- Time Complexity: O(m n). We scan the grid once to find all gates, then during BFS each cell is added to the queue at most once. Processing each cell takes O(1) work (checking 4 neighbors). Overall: O(m n).
- Space Complexity: O(m n). The queue can hold at most O(m n) cells in the worst case. No separate visited array is needed since the grid itself tracks visited status.