Solving Walls and Gates in Python: Step-by-Step Guide

Introduction to Walls and Gates

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's floor plan, you must fill each empty room with the distance to its nearest gate. Walls block movement, and unreachable rooms remain at their initial infinite value.

This problem is an excellent test of your understanding of Breadth-First Search (BFS) and multi-source traversal techniques. In this tutorial, we will break down the problem, explore multiple solution strategies, and implement an efficient Python solution step by step.

What Is the Walls and Gates Problem?

Imagine a 2D matrix where each cell can be one of three values:

-1: A wall or obstacle that cannot be passed through.
0: A gate, the destination we measure distance from.
INF (typically 2147483647): An empty room whose value must be replaced with the distance to the nearest gate.

Movement is allowed in four directions: up, down, left, and right. The goal is to update each empty room cell with the shortest distance to the nearest gate. If a room cannot reach any gate, it should remain INF.

Example Input and Output

Consider the following grid:

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

After processing, the grid should become:

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

Each empty room now holds the shortest distance to the nearest gate, while walls and gates remain unchanged.

Why This Problem Matters

The Walls and Gates problem is more than an interview exercise. It models real-world scenarios such as:

Facility layout planning: Calculating distances from rooms to exits in buildings.
Game development: Determining pathfinding distances on tile-based maps.
Robotics: Computing navigation grids for autonomous agents.
Network routing: Finding shortest paths from multiple source nodes.

Mastering this problem teaches you multi-source BFS, a technique that scales to many graph problems where you start from several origins simultaneously.

Understanding the Solution Strategy

Why Breadth-First Search?

BFS is the natural choice for shortest-path problems on unweighted graphs. Each step in BFS corresponds to moving one cell, so the first time we reach a room, we have found the shortest distance to it from a gate.

A naive approach would run BFS from each gate individually and update rooms with the minimum distance found. However, this wastes computation by revisiting rooms multiple times. A more efficient approach uses multi-source BFS, where all gates are added to the queue at once and processed level by level.

Multi-Source BFS Explained

Instead of starting from a single source, we enqueue all gates simultaneously. Each gate acts as a source at distance 0. As we expand outward, every room we discover is guaranteed to be at its shortest distance from some gate, because BFS explores in order of increasing distance.

This approach ensures each cell is visited exactly once, giving us an optimal time complexity.

Step-by-Step Implementation

Let us build the solution incrementally. We will use a collections.deque for efficient queue operations.

Step 1: Setting Up the Function Signature

We define a function that modifies the grid in place:

from collections import deque
from typing import List

def walls_and_gates(rooms: List[List[int]]) -> None:
    """
    Fill each empty room with the distance to its nearest gate.
    Modifies the grid in place.
    """
    if not rooms or not rooms[0]:
        return

We handle the edge case of an empty grid immediately to avoid index errors.

Step 2: Identifying Dimensions and Directions

Next, we capture the grid dimensions and define the four possible movement directions:

    rows, cols = len(rooms), len(rooms[0])
    
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

The directions list represents up, down, left, and right movements. Using a list of tuples keeps the code clean and easy to iterate over.

Step 3: Initializing the Queue with All Gates

We scan the entire grid and enqueue every gate's coordinates:

    queue = deque()
    
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == 0:
                queue.append((r, c))

By adding all gates at once, we set up the multi-source BFS. Each gate starts at distance 0, and the BFS will expand outward from all of them simultaneously.

Step 4: Running the BFS

Now we process the queue level by level:

    while queue:
        row, col = queue.popleft()
        
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            # Check bounds
            if 0 <= new_row < rows and 0 <= new_col < cols:
                # Only process unvisited empty rooms
                if rooms[new_row][new_col] == 2147483647:
                    rooms[new_row][new_col] = rooms[row][col] + 1
                    queue.append((new_row, new_col))

The key insight is the condition rooms[new_row][new_col] == 2147483647. We only process cells that are still marked as INF, meaning they have not been visited. Since BFS explores in order of distance, the first time we reach a room is via the shortest path, so we can safely set its distance and never revisit it.

Step 5: The Complete Solution

Putting it all together, here is the complete implementation:

from collections import deque
from typing import List

def walls_and_gates(rooms: List[List[int]]) -> None:
    """
    Fill each empty room with the distance to its nearest gate.
    Modifies the grid in place.
    
    Args:
        rooms: 2D grid where -1 is a wall, 0 is a gate,
               and 2147483647 is an empty room.
    """
    if not rooms or not rooms[0]:
        return
    
    INF = 2147483647
    rows, cols = len(rooms), len(rooms[0])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # Initialize queue with all gate positions
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == 0:
                queue.append((r, c))
    
    # Multi-source BFS
    while queue:
        row, col = queue.popleft()
        
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            if (0 <= new_row < rows and 
                0 <= new_col < cols and 
                rooms[new_row][new_col] == INF):
                rooms[new_row][new_col] = rooms[row][col] + 1
                queue.append((new_row, new_col))

Step 6: Testing the Solution

Let us verify the solution with the example from earlier:

INF = 2147483647

rooms = [
    [INF, -1,  0,  INF],
    [INF, INF, INF, -1],
    [INF, -1,  INF, -1],
    [  0, -1,  INF, INF]
]

walls_and_gates(rooms)

for row in rooms:
    print([str(cell).rjust(4) for cell in row])

Output:

['   3', '  -1', '   0', '   1']
['   2', '   2', '   1', '  -1']
['   1', '  -1', '   2', '  -1']
['   0', '  -1', '   3', '   4']

The output matches our expected result, confirming the solution works correctly.

Alternative Approach: Depth-First Search

While BFS is the optimal approach, you can also solve this problem using DFS. The idea is to start from each gate and recursively explore neighboring rooms, updating distances when a shorter path is found.

from typing import List

def walls_and_gates_dfs(rooms: List[List[int]]) -> None:
    if not rooms or not rooms[0]:
        return
    
    INF = 2147483647
    rows, cols = len(rooms), len(rooms[0])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    def dfs(row: int, col: int, distance: int) -> None:
        # Skip if out of bounds or not an improvement
        if (row < 0 or row >= rows or 
            col < 0 or col >= cols or 
            rooms[row][col] < distance):
            return
        
        rooms[row][col] = distance
        
        for dr, dc in directions:
            dfs(row + dr, col + dc, distance + 1)
    
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == 0:
                dfs(r, c, 0)

The DFS approach works but has a significant drawback: it may revisit cells multiple times when a shorter path is discovered later. This leads to a worst-case time complexity of O((m*n)^2) compared to BFS's O(m*n). Use DFS only when you need to understand all possible paths or when the grid is small.

Complexity Analysis

BFS Solution

Time Complexity: O(m * n) — Each cell is visited at most once. We scan the grid once to find gates and process each cell once during BFS.
Space Complexity: O(m * n) — In the worst case, the queue holds all cells (for example, a grid with no walls).

DFS Solution

Time Complexity: O((m * n)^2) in the worst case — Cells may be revisited multiple times as shorter paths are found.
Space Complexity: O(m * n) — The recursion stack can grow as deep as the number of cells.

For production code and interviews, the BFS approach is strongly preferred due to its guaranteed linear time complexity.

Best Practices

Use Multi-Source BFS

Always enqueue all gates at the start rather than running separate BFS from each gate. This ensures each cell is processed exactly once, giving optimal performance.

Modify In Place When Possible

The grid itself can serve as a visited tracker. By checking whether a cell still holds INF, you avoid allocating a separate visited set, reducing memory usage.

Define INF as a Named Constant

Instead of hardcoding 2147483647 throughout your code, define it as a constant. This improves readability and makes the code easier to maintain:

INF = 2147483647

Validate Input Early

Always check for empty grids at the start of your function. This prevents runtime errors and makes your code more robust:

if not rooms or not rooms[0]:
    return

Use Deque for Queue Operations

Python's collections.deque provides O(1) append and pop operations from both ends. Using a regular list with pop(0) would result in O(n) operations, significantly degrading performance.

Consider Edge Cases

Always test your solution against these scenarios:

An empty grid.
A grid with no gates (all rooms remain INF).
A grid with no rooms (only walls and gates).
A single-cell grid containing a gate.
A grid where some rooms are completely surrounded by walls and unreachable.

Common Mistakes to Avoid

Using DFS Without Distance Checks

A naive DFS that does not check whether the current distance is shorter than the existing value will loop infinitely or produce incorrect results. Always include the condition rooms[row][col] < distance to prune unnecessary recursive calls.

Forgetting Boundary Checks

Always verify that new coordinates are within the grid bounds before accessing the grid. Failing to do so results in IndexError exceptions.

Processing Walls and Gates as Rooms

Ensure your BFS only processes cells marked INF. Walls (-1) and gates (0) should never be enqueued or overwritten. The check rooms[new_row][new_col] == INF handles this naturally.

Extending the Problem

Once you understand the core solution, consider these variations to deepen your skills:

Diagonal movement: Allow movement in eight directions instead of four. Simply add the four diagonal direction tuples to the directions list.
Weighted distances: If different terrain types have different movement costs, switch to Dijkstra's algorithm using a priority queue.
Multiple gate types: Track distances to different categories of gates separately, requiring multiple distance grids.
Dynamic obstacles: If walls can appear or disappear, consider recomputing only affected regions rather than the entire grid.

Conclusion

The Walls and Gates problem is a powerful demonstration of multi-source BFS in action. By enqueuing all gates simultaneously and processing cells level by level, we achieve an elegant O(m*n) solution that visits each cell exactly once. The key takeaways are recognizing when BFS is appropriate for shortest-path problems, leveraging the grid itself as a visited tracker, and understanding why multi-source initialization outperforms running separate traversals. With the implementation and best practices covered in this guide, you are well equipped to solve this problem confidently in interviews and apply the same techniques to a wide range of graph traversal challenges.