Walls and Gates: Multiple Solutions and Complexity Analysis

Walls and Gates: Multiple Solutions and Complexity Analysis

The Walls and Gates problem is a classic graph traversal challenge frequently encountered in coding interviews and competitive programming. Given a 2D grid representing a building, you must compute the shortest distance from every empty room to the nearest gate. While the problem statement is simple, it admits several distinct algorithmic approaches — each with different trade-offs in time complexity, space complexity, and code clarity. This tutorial walks through the problem, explores multiple solutions, and analyzes their complexities so you can choose the right approach for your use case.

Problem Statement

You are given an m x n grid rooms initialized with three possible values:

• -1 — A wall or obstacle.
• 0 — A gate.
• INF — An empty room. We use 2^31 - 1 = 2147483647 to represent INF, the distance to a gate is assumed unreachable.

Your task is to fill each empty room with the distance to its nearest gate. If no gate is reachable, the value should remain INF. Distance is measured as the number of steps in a four-directional move (up, down, left, right). You must modify the grid in place.

For example, given the input:

INF  -1   0   INF
INF  INF INF  -1
INF  -1  INF  -1
  0  -1  INF  INF

The expected output is:

  3  -1   0    1
  2   2   1   -1
  1  -1   2   -1
  0  -1   3    4

Why It Matters

This problem is more than an interview exercise. It models real-world scenarios such as:

• Facility layout planning: computing walking distances to exits, restrooms, or elevators in a floor plan.
• Game development: pathfinding for AI agents navigating tile-based maps with obstacles.
• Robotics: distance field generation for obstacle-aware motion planning.
• Geographic information systems: nearest-service queries over gridded terrain.

The problem also serves as a gateway to understanding multi-source breadth-first search, a technique that generalizes to problems like "01 Matrix" (LeetCode #542) and "As Far from Land as Possible" (LeetCode #1162).

Solution 1: Multi-Source BFS (Optimal)

The key insight is that instead of running BFS from every empty room (which would be expensive), we can run BFS simultaneously from all gates at once. We enqueue every gate as a starting point with distance 0, then expand outward layer by layer. Because BFS explores nodes in order of increasing distance, the first time we reach an empty room, we have found its shortest distance to any gate.

This is the canonical optimal solution with O(m * n) time and O(m * n) space in the worst case (when the queue holds many cells).

from collections import deque

def wallsAndGates(rooms):
    if not rooms or not rooms[0]:
        return

    m, n = len(rooms), len(rooms[0])
    INF = 2147483647
    queue = deque()

    # Enqueue all gates as simultaneous BFS sources
    for r in range(m):
        for c in range(n):
            if rooms[r][c] == 0:
                queue.append((r, c))

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while queue:
        r, c = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            # Only expand into unvisited empty rooms
            if 0 <= nr < m and 0 <= nc < n and rooms[nr][nc] == INF:
                rooms[nr][nc] = rooms[r][c] + 1
                queue.append((nr, nc))

How It Works

Each gate acts as a wavefront source. The queue processes cells in non-decreasing order of distance. When a cell is dequeued, we attempt to relax its four neighbors. If a neighbor is still INF, it has not been reached by any gate's wavefront yet, so we set its distance and enqueue it. Walls (-1) and already-visited cells are skipped. Because BFS guarantees shortest paths on unweighted grids, no further relaxation is ever needed.

Complexity Analysis

• Time: O(m * n). Each cell is enqueued and dequeued at most once, and each edge (neighbor relationship) is examined at most four times.
• Space: O(m * n) in the worst case for the queue, though in practice it is bounded by the perimeter of the expanding wavefront.

Solution 2: DFS From Each Gate

An alternative is to perform a depth-first search starting from each gate. DFS is less natural for shortest-path problems because it does not explore in order of distance, but we can still make it correct by only updating a room when we find a strictly smaller distance. This approach is concise but typically slower than BFS due to redundant revisits.

def wallsAndGatesDFS(rooms):
    if not rooms or not rooms[0]:
        return

    m, n = len(rooms), len(rooms[0])
    INF = 2147483647
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    def dfs(r, c, distance):
        # Only proceed if this path offers a shorter distance
        if distance > rooms[r][c]:
            return
        rooms[r][c] = distance
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and rooms[nr][nc] != -1:
                # Only recurse if we can improve the neighbor
                if distance + 1 < rooms[nr][nc]:
                    dfs(nr, nc, distance + 1)

    for r in range(m):
        for c in range(n):
            if rooms[r][c] == 0:
                dfs(r, c, 0)

Complexity Analysis

• Time: In the worst case O((m * n)^2) because a single DFS pass may revisit cells many times as better paths are discovered. With careful pruning (the distance > rooms[r][c] guard), practical performance is better but still generally worse than BFS.
• Space: O(m * n) for the recursion stack in the worst case (a long winding path through the grid).

DFS is attractive for its brevity, but for large grids or interview settings where you must justify complexity, BFS is the safer choice.

Solution 3: Brute-Force BFS From Each Room

For completeness, consider the naive approach: for every empty room, run a BFS to find the nearest gate. This is the most intuitive but least efficient solution.

from collections import deque

def wallsAndGatesBrute(rooms):
    if not rooms or not rooms[0]:
        return

    m, n = len(rooms), len(rooms[0])
    INF = 2147483647
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    def nearest_gate(start_r, start_c):
        queue = deque([(start_r, start_c, 0)])
        visited = [[False] * n for _ in range(m)]
        visited[start_r][start_c] = True
        while queue:
            r, c, d = queue.popleft()
            if rooms[r][c] == 0:
                return d
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n \
                        and not visited[nr][nc] and rooms[nr][nc] != -1:
                    visited[nr][nc] = True
                    queue.append((nr, nc, d + 1))
        return INF

    for r in range(m):
        for c in range(n):
            if rooms[r][c] == INF:
                rooms[r][c] = nearest_gate(r, c)

Complexity Analysis

• Time: O((m * n)^2). Each of the up to m * n empty rooms triggers a BFS that may traverse the entire grid.
• Space: O(m * n) for the visited matrix and queue of each individual BFS.

This approach is included mainly to illustrate why the multi-source BFS is so valuable: by reversing the perspective (starting from gates instead of rooms), we collapse O((m * n)^2) work into O(m * n).

Comparing the Approaches

The table below summarizes the trade-offs:

Approach              | Time          | Space     | Notes
--------------------- | ------------- | --------- | ---------------------------
Multi-source BFS      | O(m * n)      | O(m * n)  | Optimal; recommended
DFS from each gate    | ~O((m*n)^2)   | O(m * n)  | Concise; redundant work
Brute-force per room  | O((m * n)^2)  | O(m * n)  | Simplest; slowest

In nearly all cases, multi-source BFS is the right answer. It is asymptotically optimal, easy to implement, and avoids the pitfalls of recursion depth or repeated work.

Best Practices

• Always validate input. Check for empty grids or grids with no rows before accessing rooms[0].
• Use a sentinel constant for INF. Defining INF = 2147483647 at the top makes the code self-documenting and avoids magic numbers.
• Prefer BFS for unweighted shortest paths. DFS can be correct but is harder to reason about and typically slower.
• Modify in place when possible. The problem asks for in-place modification, which also saves memory compared to allocating a separate distance matrix.
• Guard neighbor checks carefully. Combine bounds checks, wall checks, and visited checks in a single condition to keep the loop body clean.
• Consider bidirectional or multi-source variants for related problems. The multi-source pattern used here generalizes to many "nearest X" problems on grids and graphs.
• Test edge cases: a grid with no gates, a grid with only walls, a single-cell grid, and a grid where some rooms are unreachable from any gate.

Conclusion

The Walls and Gates problem is a compact yet rich exercise in graph traversal that rewards careful thinking about where to start the search. By shifting from a per-room BFS to a multi-source BFS launched from all gates simultaneously, we reduce the time complexity from quadratic to linear while keeping the code clean and intuitive. DFS offers a tempting shortcut but pays for it in redundant work, and the brute-force approach serves as a useful baseline for understanding why the optimal solution is so effective. Mastering this problem equips you with the multi-source BFS pattern, a versatile tool that recurs across distance-field, nearest-facility, and wave-propagation problems throughout algorithmic practice and real-world engineering.