Walls and Gates - Video Solutions

Problem Overview: You are given a grid where -1 represents walls, 0 represents gates, and INF represents empty rooms. Update each empty room with the distance to its nearest gate. If a gate cannot be reached, the room should remain INF.

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

For each empty room, run a Breadth-First Search until you find the closest gate. Start from the room, expand in four directions, and stop when a cell with value 0 is discovered. The distance traveled becomes the value for that room. Because a BFS may explore most of the grid for every empty cell, the total runtime grows to roughly O((m*n)^2). This approach is straightforward and shows understanding of shortest-path traversal on a matrix, but it repeats the same work many times.

Approach 2: BFS From Every Gate (Time: O(g*m*n), Space: O(m*n))

Instead of starting BFS from empty rooms, start from each gate and propagate distances outward. During traversal, update neighboring rooms with the minimum distance from that gate. If there are g gates, each BFS can still scan a large portion of the grid, giving worst-case complexity O(g*m*n). This improves performance when the number of gates is small, but overlapping traversals still cause repeated exploration of the same cells.

Approach 3: Multi-Source BFS (Optimal) (Time: O(m*n), Space: O(m*n))

The optimal strategy pushes all gates into the queue first and runs a single Breadth-First Search. Treat every gate as a starting node with distance 0. BFS expands level by level across the grid, updating adjacent empty rooms with current distance + 1. Because BFS guarantees the shortest path in an unweighted grid, the first time a room is reached is its minimum distance to any gate. Each cell is processed at most once, producing linear complexity O(m*n). This approach leverages the natural layer-by-layer expansion of BFS and avoids repeated scans.

The algorithm uses a queue and explores four directions for each cell: up, down, left, and right. Whenever an empty room (INF) is discovered, update it with the computed distance and push it into the queue. Walls (-1) are skipped entirely. The grid itself stores the computed distances, so no additional distance matrix is required.

Recommended for interviews: Multi-source BFS is the expected solution. It demonstrates strong understanding of shortest-path problems in a grid and efficient use of array-based matrix traversal. Mentioning the brute-force BFS first shows problem exploration, but implementing the multi-source approach proves you can optimize redundant graph traversals.