LeetCode 286 - Walls and Gates

LeetCode Problem 286

Difficulty: 🟡 Medium
Topics: Array, Breadth-First Search, Matrix

Solution

Problem Understanding

The problem gives us a 2D grid called rooms, where each cell represents one of three possible states.

A value of -1 represents a wall or obstacle that cannot be passed through.

A value of 0 represents a gate.

A value of 2147483647, which is referred to as INF, represents an empty room whose distance to the nearest gate has not yet been determined.

The task is to modify the grid in place so that every empty room contains the distance to its nearest gate. Distance is measured using standard grid movement rules, meaning we can move one step at a time in the four cardinal directions: up, down, left, and right.

If a room cannot reach any gate because walls block all possible paths, it must remain INF.

The important detail is that the grid must be updated in place. We are not supposed to return a new matrix.

The constraints are significant:

• m and n can each be as large as 250
• The grid may therefore contain up to 62,500 cells

This size immediately suggests that expensive repeated traversals could become too slow. Any solution significantly worse than O(m * n) may struggle under worst case conditions.

Several edge cases are important:

• A grid may contain no gates at all, in which case every empty room stays INF
• A grid may contain only walls
• A grid may contain rooms completely isolated by walls
• Multiple gates may exist, and a room must choose the shortest distance among all reachable gates
• The grid can be as small as 1 x 1

The core challenge is efficiently finding the shortest distance from every room to the nearest gate without repeatedly recomputing paths.

Approaches

Brute Force Approach

A straightforward solution is to process every empty room independently.

For each cell containing INF, we could run a Breadth-First Search to locate the nearest gate. Since BFS naturally explores positions level by level, the first gate encountered would give the shortest distance.

This approach is correct because BFS guarantees shortest path distances in an unweighted grid.

However, the problem is efficiency.

Suppose there are k empty rooms. For each room, we may end up traversing most of the grid. In the worst case:

• There are O(m * n) empty rooms
• Each BFS costs O(m * n)

This leads to a total complexity of:

O((m * n)^2)

With up to 62,500 cells, this becomes far too expensive.

Optimal Approach

The key observation is that the problem can be reversed.

Instead of starting a BFS from every empty room and searching for a gate, we can start BFS simultaneously from all gates and expand outward.

This works because BFS explores positions in increasing order of distance.

When a room is first reached during this multi-source BFS, we know that:

• It has been reached by the closest possible gate
• The current BFS layer represents the shortest distance

This transforms the problem into a single traversal of the grid.

The idea is called multi-source BFS because multiple starting points, all gates, are inserted into the queue initially.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((m * n)^2)	O(m * n)	Run BFS separately from every empty room
Optimal	O(m * n)	O(m * n)	Multi-source BFS starting from all gates simultaneously

Algorithm Walkthrough

1. Initialize a queue for BFS traversal.

BFS is the correct choice because all moves have equal cost. BFS guarantees that the first time we reach a room, we have found the shortest possible distance. 2. Scan the entire grid and add every gate to the queue.

Every cell containing 0 becomes a starting point for BFS. This is the critical optimization. Instead of searching for gates from rooms, we spread outward from all gates at once. 3. Process the queue until it becomes empty.

Each queue entry represents a cell whose shortest distance is already known. 4. For the current cell, examine its four neighboring positions.

The four valid directions are:

• up
• down
• left
• right

5. Skip invalid neighbors.

A neighbor should be ignored if:

• it is outside grid boundaries
• it is a wall
• it has already been assigned a distance

We only want to visit cells still equal to INF. 6. Update reachable empty rooms.

If a neighboring cell is INF, assign:

rooms[next_row][next_col] = rooms[current_row][current_col] + 1

This works because the current cell already stores the shortest distance to a gate. 7. Add the updated room to the queue.

This allows BFS expansion to continue outward level by level. 8. Continue until all reachable rooms have been processed.

Any room never reached remains INF, which correctly indicates no path to a gate exists.

Why it works

BFS explores cells in increasing order of distance from the starting points. Because all gates are inserted into the queue initially, the search expands outward uniformly from every gate at the same time.

The first time a room is visited, it is guaranteed to be reached through the shortest possible path from the nearest gate. Any alternative path would either have equal or greater length and therefore would be processed later in BFS order.

This invariant guarantees correctness.

Python Solution

from collections import deque
from typing import List

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        
        if not rooms or not rooms[0]:
            return
        
        rows = len(rooms)
        cols = len(rooms[0])
        
        queue = deque()
        
        # Add all gates to the queue
        for row in range(rows):
            for col in range(cols):
                if rooms[row][col] == 0:
                    queue.append((row, col))
        
        directions = [
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1)
        ]
        
        # Multi-source BFS
        while queue:
            row, col = queue.popleft()
            
            for dr, dc in directions:
                next_row = row + dr
                next_col = col + dc
                
                # Skip invalid positions
                if (
                    next_row < 0
                    or next_row >= rows
                    or next_col < 0
                    or next_col >= cols
                ):
                    continue
                
                # Only process empty rooms
                if rooms[next_row][next_col] != 2147483647:
                    continue
                
                # Update distance
                rooms[next_row][next_col] = rooms[row][col] + 1
                
                # Continue BFS
                queue.append((next_row, next_col))

The implementation begins by handling the edge case of an empty grid.

Next, we compute the grid dimensions and create a queue using deque, which provides efficient O(1) insertions and removals from both ends.

The first nested loop scans the matrix and inserts every gate into the queue. This establishes the multi-source BFS setup.

The directions list centralizes movement logic so neighbor traversal remains concise and maintainable.

Inside the BFS loop, we remove one cell from the queue and inspect all four neighboring cells.

Boundary checks ensure we do not access invalid indices.

We only process cells still equal to 2147483647. This condition serves two purposes:

• It identifies unvisited empty rooms
• It prevents revisiting cells whose shortest distance has already been assigned

When a valid room is found, we assign its distance as the current cell's distance plus one. Because BFS expands level by level, this guarantees the shortest path.

Finally, the updated room is pushed into the queue so its neighbors can later be explored.

Go Solution

func wallsAndGates(rooms [][]int) {
    if len(rooms) == 0 || len(rooms[0]) == 0 {
        return
    }

    rows := len(rooms)
    cols := len(rooms[0])

    type Cell struct {
        row int
        col int
    }

    queue := []Cell{}

    // Add all gates to the queue
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if rooms[r][c] == 0 {
                queue = append(queue, Cell{r, c})
            }
        }
    }

    directions := [][]int{
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1},
    }

    front := 0

    // Multi-source BFS
    for front < len(queue) {
        current := queue[front]
        front++

        for _, dir := range directions {
            nextRow := current.row + dir[0]
            nextCol := current.col + dir[1]

            // Boundary check
            if nextRow < 0 ||
                nextRow >= rows ||
                nextCol < 0 ||
                nextCol >= cols {
                continue
            }

            // Only process empty rooms
            if rooms[nextRow][nextCol] != 2147483647 {
                continue
            }

            // Update distance
            rooms[nextRow][nextCol] = rooms[current.row][current.col] + 1

            // Continue BFS
            queue = append(queue, Cell{nextRow, nextCol})
        }
    }
}

The Go implementation follows the same algorithmic structure as the Python version.

One notable difference is queue management. Instead of using a dedicated deque structure, the implementation uses a slice with a front pointer. This avoids expensive slice shifting operations.

Go does not provide tuples, so a small Cell struct is used to store coordinates.

The solution modifies the input matrix directly, just like the Python version.

Because the problem guarantees distances smaller than 2147483647, adding 1 during BFS cannot overflow under valid inputs.

Worked Examples

Example 1

Input:

[
  [INF, -1, 0, INF],
  [INF, INF, INF, -1],
  [INF, -1, INF, -1],
  [0, -1, INF, INF]
]

Initial queue after scanning gates:

Queue
(0,2), (3,0)

Step 1

Process (0,2).

Reachable neighbors:

• (1,2) becomes 1
• (0,3) becomes 1

Grid becomes:

Row	Values
0	[INF, -1, 0, 1]
1	[INF, INF, 1, -1]
2	[INF, -1, INF, -1]
3	[0, -1, INF, INF]

Queue:

Queue
(3,0), (1,2), (0,3)

Step 2

Process (3,0).

Reachable neighbor:

• (2,0) becomes 1

Grid:

Row	Values
0	[INF, -1, 0, 1]
1	[INF, INF, 1, -1]
2	[1, -1, INF, -1]
3	[0, -1, INF, INF]

Queue:

Queue
(1,2), (0,3), (2,0)

Step 3

Process (1,2).

Reachable neighbors:

• (2,2) becomes 2
• (1,1) becomes 2

Grid:

Row	Values
0	[INF, -1, 0, 1]
1	[INF, 2, 1, -1]
2	[1, -1, 2, -1]
3	[0, -1, INF, INF]

Continuing BFS

The algorithm continues level by level until all reachable rooms are assigned.

Final result:

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

Example 2

Input:

[[-1]]

The grid contains only a wall.

No gates are added to the queue.

BFS never begins, and the grid remains unchanged:

[[-1]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n)	Each cell is processed at most once
Space	O(m * n)	Queue may contain many cells in worst case

The BFS visits every room at most one time. Once a room receives its shortest distance, it is never revisited.

Since the grid contains m * n cells, total processing work is linear in the size of the grid.

The queue can grow to contain many cells simultaneously, especially in open grids with few walls, leading to O(m * n) auxiliary space usage.

Test Cases

from typing import List

INF = 2147483647

def run_test(rooms: List[List[int]], expected: List[List[int]]):
    Solution().wallsAndGates(rooms)
    assert rooms == expected

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

expected = [
    [3, -1, 0, 1],
    [2, 2, 1, -1],
    [1, -1, 2, -1],
    [0, -1, 3, 4]
]

run_test(rooms, expected)  # Standard multi-gate example

# Example 2
rooms = [[-1]]
expected = [[-1]]

run_test(rooms, expected)  # Single wall cell

# Single gate
rooms = [[0]]
expected = [[0]]

run_test(rooms, expected)  # Grid already contains only a gate

# No gates
rooms = [
    [INF, INF],
    [INF, INF]
]

expected = [
    [INF, INF],
    [INF, INF]
]

run_test(rooms, expected)  # Unreachable rooms remain INF

# Fully blocked rooms
rooms = [
    [0, -1],
    [-1, INF]
]

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

run_test(rooms, expected)  # Room isolated by walls

# One-dimensional row
rooms = [[0, INF, INF, INF]]

expected = [[0, 1, 2, 3]]

run_test(rooms, expected)  # Horizontal BFS expansion

# One-dimensional column
rooms = [
    [0],
    [INF],
    [INF]
]

expected = [
    [0],
    [1],
    [2]
]

run_test(rooms, expected)  # Vertical BFS expansion

# Multiple gates
rooms = [
    [0, INF, INF],
    [INF, INF, INF],
    [INF, INF, 0]
]

expected = [
    [0, 1, 2],
    [1, 2, 1],
    [2, 1, 0]
]

run_test(rooms, expected)  # Distances chosen from nearest gate

Test Summary

Test	Why
Standard multi-gate grid	Validates core BFS logic
Single wall cell	Ensures walls remain unchanged
Single gate	Confirms gates remain zero
No gates	Verifies unreachable rooms stay INF
Isolated room	Tests wall blocking behavior
One-dimensional row	Validates horizontal traversal
One-dimensional column	Validates vertical traversal
Multiple gates	Confirms nearest gate distance is selected

Edge Cases

No Gates in the Grid

If the matrix contains no gates, the BFS queue starts empty. A naive implementation might incorrectly modify rooms or crash due to assumptions about queue contents.

This implementation handles the case naturally. Since no gates are inserted into the queue, the BFS loop never executes, and all empty rooms remain INF.

Rooms Completely Blocked by Walls

Some rooms may be surrounded by walls and therefore unable to reach any gate.

A buggy solution might accidentally assign distances through invalid paths or overwrite unreachable rooms.

This implementation only propagates distances through valid BFS traversal. Since blocked rooms are never reached, they correctly remain INF.

Multiple Gates Competing for the Same Room

A room may be reachable from several gates with different distances.

A naive repeated-search solution may recompute distances many times or accidentally overwrite shorter distances with longer ones.

The multi-source BFS guarantees correctness because BFS explores cells in increasing distance order. The first time a room is visited, it is necessarily through the shortest path from the nearest gate. Subsequent longer paths are ignored because the room is no longer INF.