Walls and Gates

Medium · Graphs · Explanation and code example

Multi Source BFS

How it works

Instead of running BFS from every empty room, run BFS once starting from all gates (0 cells) at the same time.

Why this works:

  • BFS spreads out in "waves" of distance 0, 1, 2, ...
  • If we start the queue with all gates, the first time the wave reaches an empty cell, it must be from the closest gate (because BFS guarantees the first visit is the shortest distance in an unweighted grid). So each cell gets filled with its minimum distance to any gate.

This avoids repeated work and is the optimal approach.

Steps

  1. Put all gate cells (grid[r][c] == 0) into a queue.
  2. Mark them visited. Walls (-1) are never added.
  3. Set dist = 0.
  4. While the queue is not empty:
    • Process all nodes currently in the queue (this is one BFS level = distance dist).
    • For each cell popped:
      • Set grid[r][c] = dist (distance to nearest gate).
      • Try its 4 neighbors:
        • If in bounds, not a wall, and not visited -> mark visited and push to queue.
    • After finishing the level, do dist += 1.
  5. After BFS ends, every reachable empty room has been updated with its shortest distance; unreachable rooms remain INF.

Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

Where m is the number of rows and n is the number of columns in the grid.

Things to watch for

Starting BFS from Empty Rooms Instead of Gates

A common mistake is to run BFS from each empty room to find the nearest gate, resulting in O((m*n)^2) time complexity. The optimal approach is multi-source BFS starting from all gates simultaneously, which processes each cell exactly once.

Not Distinguishing Walls from Unvisited Cells

Walls are represented by -1 and should never be added to the queue or updated. Confusing the wall value with the infinity value (2147483647) for empty rooms can cause incorrect distance calculations or infinite loops.

Python code example

from typing import List
from collections import deque

class Solution:
    def wallsAndGates(self, grid: List[List[int]]) -> None:
        ROWS, COLS = len(grid), len(grid[0])
        visit = set()
        q = deque()

        def addCell(r, c):
            if (min(r, c) < 0 or r == ROWS or c == COLS or
                (r, c) in visit or grid[r][c] == -1
            ):
                return
            visit.add((r, c))
            q.append([r, c])

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 0:
                    q.append([r, c])
                    visit.add((r, c))

        dist = 0
        while q:
            for i in range(len(q)):
                r, c = q.popleft()
                grid[r][c] = dist
                addCell(r + 1, c)
                addCell(r - 1, c)
                addCell(r, c + 1)
                addCell(r, c - 1)
            dist += 1

C++ code example

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        queue<pair<int, int>> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    q.push({i, j});
                }
            }
        }

        vector<vector<int>> dirs = {{-1, 0}, {1, 0},
                                    {0, -1}, {0, 1}};
        while (!q.empty()) {
            int row = q.front().first;
            int col = q.front().second;
            q.pop();

            for (int i = 0; i < 4; i++) {
                int r = row + dirs[i][0];
                int c = col + dirs[i][1];

                if (r < 0 || r >= m || c < 0 ||
                    c >= n || grid[r][c] != INT_MAX) {
                    continue;
                }

                grid[r][c] = grid[row][col] + 1;
                q.push({r, c});
            }
        }
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations