Walls and Gates (LeetCode 286)

The problem

You get a grid where -1 is a wall, 0 is a gate, and INF (2147483647) is an empty room. Fill each empty room, in place, with the number of steps to its nearest gate, moving up, down, left or right through non-wall cells. A room that can’t reach any gate stays INF.

Input:                     Output:
INF  -1   0  INF           3  -1   0   1
INF INF INF  -1            2   2   1  -1
INF  -1 INF  -1            1  -1   2  -1
  0  -1 INF INF            0  -1   3   4

The top-left room is 3 steps from the gate in the bottom-left corner, which is closer than the gate at the top.

How to think about it

Start with brute force. Run a BFS from each room until it hits a gate. Each search can cover the whole grid, so with R·C rooms that’s O((R·C)²). Alternatively, BFS from each gate and keep the minimum per room: O(G·R·C) for G gates, still too slow when there are many gates.

The key insight: start one BFS from every gate at the same time. Put all gates in the queue before you begin. BFS expands in rings: first every cell at distance 1 from some gate, then every cell at distance 2, and so on. So the first time any room is reached, it’s reached by its nearest gate, and that distance is final. You never need to update a room twice, and the whole grid is processed once.

The grid doubles as the visited set. A room still holding INF hasn’t been reached. Once you write a distance into it, it’s no longer INF, so it won’t be enqueued again. Walls (-1) and gates (0) are never INF, so they’re skipped automatically.

Which pattern is this? Multi-source BFS. The tell is “distance to the nearest of several sources” on an unweighted grid. Rotting Oranges is the same idea, counting rounds instead of storing distances.

Approach

1. Scan the grid and push every gate (r, c) into a queue.
2. Pop a cell. For each of its four neighbours that is in bounds and still INF, set it to the current cell’s value plus one and push it.
3. Repeat until the queue is empty. Rooms never reached keep INF.

Solution

from collections import deque
def walls_and_gates(rooms):
    R, C = len(rooms), len(rooms[0]); INF = 2147483647; q = deque()
    for r in range(R):
        for c in range(C):
            if rooms[r][c] == 0: q.append((r, c))          # every gate is a starting point
    while q:
        r, c = q.popleft()
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r+dr, c+dc
            if 0 <= nr < R and 0 <= nc < C and rooms[nr][nc] == INF:   # unvisited room only
                rooms[nr][nc] = rooms[r][c] + 1; q.append((nr, nc))   # first visit = shortest
    return rooms
# walls_and_gates([[INF,-1,0,INF],[INF,INF,INF,-1],[INF,-1,INF,-1],[0,-1,INF,INF]])
#   -> [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Dry run

On the example grid, the queue starts with both gates: [(0,2), (3,0)].

The remaining pops fill nothing new. Nine rooms get a distance, and each was written exactly once.

Complexity

• Time: O(R·C). Every cell enters the queue at most once and checks four neighbours.
• Space: O(R·C) for the queue in the worst case (for example, a grid full of gates).

Edge cases and pitfalls

• No gates: the queue starts empty and every room stays INF.
• Unreachable rooms behind walls stay INF, which is the expected output. In [[INF, -1], [-1, 0]] the top-left room is walled off.
• One BFS per gate with a minimum update gives the right answer but costs O(G·R·C). Interviewers want the multi-source version.
• DFS doesn’t work here without extra care: depth-first reaches a room by a long path first, so you’d have to keep revisiting and lowering values.
• Empty grid: this code assumes at least one row (rooms[0]). Add a guard if empty input is possible.

Related problems

• Rotting Oranges (LeetCode 994): multi-source BFS that counts minutes until every orange rots.
• Word Ladder (LeetCode 127): BFS for the shortest number of steps on an implicit graph.
• Surrounded Regions (LeetCode 130): another grid search started from many cells at once.