Walls and Gates - Solution & Explanation

Problem Overview: You are given a 2D grid representing rooms, gates, and walls. Each empty room must be filled with the distance to its nearest gate. Walls block movement, and if a gate cannot be reached the value remains unchanged.

This is fundamentally a shortest-path problem on a grid. Each move to an adjacent cell (up, down, left, right) costs one step. The goal is to compute the minimum distance from every empty room to the closest gate efficiently.

Approach 1: BFS From Every Empty Room (Brute Force) (Time: O((mn)^2), Space: O(mn))

For every empty room, run a Breadth-First Search until you hit a gate. BFS guarantees the first gate found is the closest because it expands level by level. However, you repeat the same exploration for many cells, causing massive overlap. On an matrix with m * n cells, each BFS can scan most of the grid, leading to quadratic behavior. This approach works for small grids but times out on larger inputs.

Approach 2: DFS From Each Gate (Time: O(mn), Space: O(mn))

Another idea is to start from each gate and spread distances using depth-first search. The DFS recursively explores neighbors while tracking distance. When reaching a room, update it only if the current path gives a shorter distance than the stored value. This avoids recomputing from every empty room, but DFS may revisit cells multiple times and recursion depth can grow large. While workable, it is harder to control updates and less predictable than BFS for shortest-path problems.

Approach 3: Multi-Source BFS From All Gates (Optimal) (Time: O(mn), Space: O(mn))

The optimal solution reverses the perspective: start BFS simultaneously from all gates. Push every gate into a queue with distance 0, then expand outward level by level. When visiting neighbors, update an empty room only if its value is still INF, then set it to current_distance + 1 and enqueue it. Because BFS expands in layers, the first time a room is reached is guaranteed to be the shortest distance to any gate.

This approach visits each cell at most once. Every expansion processes four neighbors and updates the grid directly. The algorithm runs in O(mn) time and uses O(mn) space for the queue in the worst case. The logic mirrors classic shortest path problems on grids and heavily relies on queue-based BFS traversal over an array-backed matrix.

Recommended for interviews: Multi-source BFS from all gates. It demonstrates strong intuition about reversing the search direction to avoid redundant work. Mentioning the brute-force BFS shows you understand the baseline, but implementing the multi-source BFS shows you recognize optimal graph traversal patterns used in grid shortest-path problems.