Walls and Gates

LeetCode 286: Walls and Gates Solution & Explanation

Problem Overview

TL;DR: Use multi-source breadth-first search starting from every gate simultaneously, assigning each reachable empty room its minimum distance while leaving walls and unreachable rooms unchanged.

The LeetCode 286 Solution treats the grid as an unweighted graph: each non-wall cell is a vertex, and horizontal or vertical adjacency creates an edge. All gates are inserted into one queue initially, so BFS expands outward from every gate in distance order. The grid is modified in place, making this an optimal solution for interviews and a popular interview question.

For Walls and Gates, the values have fixed meanings:

• -1: wall, which cannot be entered
• 0: gate
• 2147483647: empty room whose distance is not yet known

Every reachable empty room must contain its minimum number of moves to any gate. Empty rooms without a valid route remain 2147483647.

Brute Force Approach for Walls and Gates

A naive solution can process each empty room independently:

1. Start a BFS from the empty room.
2. Stop when a gate is found.
3. Record the distance to the closest gate.
4. Repeat for every empty room.

Because movement is allowed only through non-wall cells, each individual BFS must track visited cells and avoid crossing walls.

Naive Pseudocode

for every cell (row, col):
    if rooms[row][col] is an empty room:
        create an empty queue
        mark (row, col) as visited
        enqueue (row, col, 0)

        while queue is not empty:
            current = dequeue()

            if current is a gate:
                rooms[row][col] = current.distance
                stop this BFS

            for each of the four neighbors:
                if neighbor is in bounds
                   and neighbor is not a wall
                   and neighbor is not visited:
                    mark neighbor as visited
                    enqueue neighbor with distance + 1

Let R be the number of rows and C the number of columns. One BFS can visit O(RC) cells. In the worst case, there are O(RC) empty rooms, so the total time complexity is:

O(RC · RC) = O(R²C²)

The grid can contain up to 250 × 250 = 62,500 cells. Repeating a full traversal for many empty rooms causes excessive work and can result in Time Limit Exceeded. The same reachable regions are explored repeatedly instead of sharing distance information between rooms.

Algorithm Strategy: Graph Traversal Patterns (DFS & BFS)

1. Scan the entire grid.
2. Add every gate to a FIFO queue.
3. Repeatedly remove the cell at the front of the queue.
4. Examine its four neighboring positions.
5. Ignore neighbors that:
   • Fall outside the grid.
   • Are walls.
   • Are gates or rooms that already have a finite distance.
6. For an unvisited empty room, assign its value to the current room's distance plus one.
7. Add the newly updated room to the queue.
8. Continue until the queue is empty.

The grid itself stores the visited state and the computed distance. No separate visited matrix is required.

Execution Flow

1. Initialize the queue

   • Scan every cell.
   • Enqueue all cells whose value is 0.
   • Their distances are already finalized as zero.

2. Process the next BFS position

   • Remove the oldest cell from the queue.
   • Because the queue is FIFO, cells are processed in nondecreasing distance order.

3. Check four directions

   • Compute the neighboring row and column for up, down, left, and right.
   • Reject positions outside the rectangular grid.

4. Enforce cell constraints

   • Continue without processing if the neighbor is not 2147483647.
   • This excludes walls, gates, and rooms already assigned a distance.

5. Assign the shortest known distance

   • Set the neighbor to the current room's value plus 1.
   • Enqueue the neighbor for later expansion.

6. Finish

   • When the queue is empty, every reachable empty room has been assigned.
   • Walls and gates retain their original values.
   • Unreachable empty rooms were never enqueued and remain 2147483647.

Proof of Correctness

We prove that the algorithm assigns every reachable empty room its minimum distance to any gate.

All gates are inserted into the queue with distance 0. Therefore, the initial BFS layer contains every possible source.

Assume BFS is processing cells in nondecreasing distance order. When a room with distance d is removed from the queue, every cell with distance less than or equal to d that is reachable through valid cells has already been processed. Any unvisited neighboring empty room is therefore reachable in d + 1 moves.

The algorithm assigns that neighbor d + 1 and immediately treats it as visited. Since no later queue entry can have a distance smaller than d, no future path can reach the room with a smaller distance. Thus, its first assigned value is optimal.

By induction over BFS processing order, every reachable empty room receives the minimum distance from any gate. Walls are never entered because only cells with value 2147483647 are expanded into. Any empty room that cannot be reached from a gate is never discovered, so it correctly remains 2147483647.

Therefore, the algorithm produces the required final grid.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 542: 01 Matrix
• LeetCode 127: Word Ladder
• LeetCode 1091: Shortest Path in Binary Matrix
• LeetCode 994: Rotting Oranges

They all use BFS to process an unweighted state graph in increasing distance or time order. Depending on the problem, BFS begins from multiple zero-distance cells, a single source, or all initially active cells. In each case, the queue and visited-state invariant prevent repeated traversal and preserve the first optimal discovery.

Reference Implementation

C++ Solution for LeetCode 286

1class Solution {
2public:
3    void wallsAndGates(std::vector<std::vector<int>>& rooms) {
4        if (rooms.empty() || rooms[0].empty()) {
5            return;
6        }
7
8        const int rows = static_cast<int>(rooms.size());
9        const int cols = static_cast<int>(rooms[0].size());
10        const int INF = 2147483647;
11        std::queue<std::pair<int, int>> gates;
12
13        for (int r = 0; r < rows; ++r) {
14            for (int c = 0; c < cols; ++c) {
15                if (rooms[r][c] == 0) {
16                    gates.push({r, c});
17                }
18            }
19        }
20
21        const int dr[4] = {-1, 1, 0, 0};
22        const int dc[4] = {0, 0, -1, 1};
23
24        while (!gates.empty()) {
25            auto [r, c] = gates.front();
26            gates.pop();
27
28            for (int direction = 0; direction < 4; ++direction) {
29                int nr = r + dr[direction];
30                int nc = c + dc[direction];
31
32                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols ||
33                    rooms[nr][nc] != INF) {
34                    continue;
35                }
36
37                rooms[nr][nc] = rooms[r][c] + 1;
38                gates.push({nr, nc});
39            }
40        }
41    }
42};

The C++ implementation uses the grid value 2147483647 as the unvisited marker. Once an empty room is assigned a distance, it cannot be enqueued again.

Java Solution for LeetCode 286

1class Solution {
2    public void wallsAndGates(int[][] rooms) {
3        if (rooms == null || rooms.length == 0 || rooms[0] == null || rooms[0].length == 0) {
4            return;
5        }
6
7        int rows = rooms.length;
8        int cols = rooms[0].length;
9        java.util.ArrayDeque<int[]> queue = new java.util.ArrayDeque<>();
10
11        for (int row = 0; row < rows; row++) {
12            for (int col = 0; col < cols; col++) {
13                if (rooms[row][col] == 0) {
14                    queue.offer(new int[] {row, col});
15                }
16            }
17        }
18
19        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
20
21        while (!queue.isEmpty()) {
22            int[] position = queue.poll();
23            int row = position[0];
24            int col = position[1];
25
26            for (int[] direction : directions) {
27                int nextRow = row + direction[0];
28                int nextCol = col + direction[1];
29
30                if (nextRow >= 0 && nextRow < rows
31                        && nextCol >= 0 && nextCol < cols
32                        && rooms[nextRow][nextCol] == 2147483647) {
33                    rooms[nextRow][nextCol] = rooms[row][col] + 1;
34                    queue.offer(new int[] {nextRow, nextCol});
35                }
36            }
37        }
38    }
39}

The Java solution uses ArrayDeque as the FIFO queue. Each queued array stores a room's row and column, while the grid stores the distance and visited state.

Python Solution for LeetCode 286

1from collections import deque
2from typing import List, Optional
3
4
5class Solution:
6    def wallsAndGates(self, rooms: List[List[int]]) -> None:
7        """Do not return anything; modify rooms in-place instead."""
8        if not rooms or not rooms[0]:
9            return
10
11        rows = len(rooms)
12        cols = len(rooms[0])
13        queue = deque()
14
15        for row in range(rows):
16            for col in range(cols):
17                if rooms[row][col] == 0:
18                    queue.append((row, col))
19
20        directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
21
22        while queue:
23            row, col = queue.popleft()
24
25            for row_delta, col_delta in directions:
26                next_row = row + row_delta
27                next_col = col + col_delta
28
29                if (
30                    0 <= next_row < rows
31                    and 0 <= next_col < cols
32                    and rooms[next_row][next_col] == 2147483647
33                ):
34                    rooms[next_row][next_col] = rooms[row][col] + 1
35                    queue.append((next_row, next_col))

The Python implementation uses deque.popleft() for constant-time FIFO removal. It follows the same multi-source BFS invariant as the C++ and Java versions.