Tech Blogs LLD SDE Playbook DSA

Walls and Gates

Medium Top 250
Associated Patterns
Graphs
Interviewed At (Company Tags)
MetaGoogleAmazon
External Reference View on LeetCode

Problem Description

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

  • -1 — A wall or an obstacle
  • 0 — A gate
  • INF — Infinity means an empty room. We use 2^31 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should remain INF.

Examples

Example 1:

Input: INF -1 0 INF INF INF INF -1 INF -1 INF -1 0 -1 INF INF Output: 3 -1 0 1 2 2 1 -1 1 -1 2 -1 0 -1 3 4

Constraints

  • m == rooms.length
  • n == rooms[i].length
  • 1 ≤ m, n ≤ 250
  • rooms[i][j] is -1, 0, or 2^31 - 1

BFS From All Gates Simultaneously

If you run BFS from each gate independently, you do O(gates * m * n) work. The smarter approach: seed the queue with all gates at once and run one BFS. Each room gets filled with the BFS level at which it’s first reached, which is exactly its distance to the nearest gate.

This is the same multi-source BFS pattern as Rotting Oranges.

Solution: Multi-Source BFS

import java.util.*;

class Solution {
    public void wallsAndGates(int[][] rooms) {
        int rows = rooms.length, cols = rooms[0].length;
        Queue<int[]> queue = new LinkedList<>();

        // seed all gates
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (rooms[r][c] == 0) queue.offer(new int[]{r, c});
            }
        }

        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int nr = cell[0] + d[0], nc = cell[1] + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && rooms[nr][nc] == Integer.MAX_VALUE) {
                    rooms[nr][nc] = rooms[cell[0]][cell[1]] + 1;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
    }
}
from collections import deque

class Solution:
    def wallsAndGates(self, rooms: list[list[int]]) -> None:
        if not rooms:
            return
        rows, cols = len(rooms), len(rooms[0])
        INF = 2147483647
        queue = deque()

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

        dirs = [(1,0),(-1,0),(0,1),(0,-1)]
        while queue:
            r, c = queue.popleft()
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == INF:
                    rooms[nr][nc] = rooms[r][c] + 1
                    queue.append((nr, nc))
#include <vector>
#include <queue>
#include <climits>

class Solution {
public:
    void wallsAndGates(std::vector<std::vector<int>>& rooms) {
        int rows = rooms.size(), cols = rooms[0].size();
        std::queue<std::pair<int,int>> q;

        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                if (rooms[r][c] == 0) q.push({r, c});

        int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && rooms[nr][nc] == INT_MAX) {
                    rooms[nr][nc] = rooms[r][c] + 1;
                    q.push({nr, nc});
                }
            }
        }
    }
};

Complexity Analysis:

  • Time Complexity: O(m * n). Each cell is visited at most once.
  • Space Complexity: O(m * n) for the queue.

Where it breaks: the check rooms[nr][nc] == INT_MAX (or == INF) serves as the visited check. A cell with a distance already assigned won’t be re-queued, so you don’t need a separate visited array. Walls (-1) are also skipped since they’re not INF.

Common Mistakes

  • Running BFS from each gate separately. This gives the right answer but is O(gates * m * n) in the worst case. Multi-source BFS is always O(m * n).
  • Using a DFS. DFS doesn’t guarantee shortest paths. The first time DFS visits a room, it might not have found the shortest path to that room.

← All Problems