150NeetCode 150

86.Walls and Gates

MediumGraphs · 7/19
LeetCode #286Video

Problem

You are given an m x n grid rooms where each cell holds one of three values:

  • -1 — a wall or obstacle,
  • 0 — a gate,
  • INF = 2147483647 (Integer.MAX_VALUE) — an empty room.

Fill each empty room with the distance to its nearest gate, moving one step at a time up, down, left or right and never through walls. If a room cannot reach any gate, leave it as INF. Modify rooms in place; the method returns nothing.

Examples

Input:  rooms = [
  [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]
]
Explanation: e.g. (0,0) is 3 steps from the gate at (3,0); (3,3) is 4 steps from the gate at (0,2).
Input:  rooms = [[-1]]
Output: [[-1]]
Explanation: There are no empty rooms to fill.
Input:  rooms = [
  [INF, -1],
  [ -1,  0]
]
Output: [
  [INF, -1],
  [ -1,  0]
]
Explanation: The room at (0,0) is walled off from the only gate, so it stays INF.

Constraints

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

💡 Key Insight

The distance from a room to its nearest gate is a shortest path in an unweighted grid, which BFS computes. Running BFS per room or per gate repeats work. Instead, put all gates into one queue at distance 0 and run a single multi-source BFS. BFS reaches cells in increasing order of distance, so the first time any gate's wave reaches an empty room, that is already the nearest-gate distance — the room can be filled and never touched again. Every cell is processed once: O(m·n).

Brute Force (BFS from Each Room)

TimeO((m·n)²)SpaceO(m·n)

Intuition

Answer the question directly for every empty room: BFS outward from it until the first gate is found. BFS guarantees the first gate found is the closest one. Every room repeats a search over much of the grid.

Algorithm

  1. For each cell with value INF:
    • BFS from it with a fresh visited array, tracking steps.
    • When a popped cell is a gate (0), write its step count into the room and stop.
    • If the BFS ends without a gate, leave the room as INF.

Visualization

Room (0,0), BFS rings:
  step 1: (1,0)              (0,1) is a wall
  step 2: (2,0), (1,1)
  step 3: (3,0) = gate  →  rooms[0][0] = 3

Code

java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    private static final int INF = Integer.MAX_VALUE;
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public void wallsAndGates(int[][] rooms) {
        for (int r = 0; r < rooms.length; r++) {
            for (int c = 0; c < rooms[0].length; c++) {
                if (rooms[r][c] == INF) {
                    rooms[r][c] = nearestGate(rooms, r, c);
                }
            }
        }
    }

    // Plain BFS from one room; returns steps to the first gate (or INF)
    private int nearestGate(int[][] rooms, int sr, int sc) {
        int rows = rooms.length, cols = rooms[0].length;
        boolean[][] visited = new boolean[rows][cols];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{sr, sc, 0});
        visited[sr][sc] = true;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            if (rooms[cur[0]][cur[1]] == 0) {
                return cur[2]; // first gate reached is the nearest
            }
            for (int[] d : DIRS) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && !visited[nr][nc] && rooms[nr][nc] != -1) {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc, cur[2] + 1});
                }
            }
        }
        return INF;
    }
}

Complexity

  • Time: O((m·n)²) — up to m·n rooms, each BFS may scan the whole grid.
  • Space: O(m·n) — visited and the queue of one BFS.

Complexity Comparison

Approach Time Space
BFS from Each Room O((m·n)²) O(m·n)
BFS from Each Gate O(k·m·n) O(m·n)
Multi-Source BFS O(m·n) O(m·n)

Common Pitfalls

  • Using DFS from each gate without a "strictly better" check — it can revisit cells an exponential number of times or write a non-shortest distance.
  • Writing the distance when a cell is popped instead of when it is pushed; the same room is then enqueued several times.
  • Computing INF + 1 — adding to Integer.MAX_VALUE overflows to a negative number. Only add 1 to cells that already hold a real distance.
  • Moving into gates or walls: only cells equal to INF (multi-source) or larger than the new distance (per gate) should be updated.
  • Expecting unreachable rooms to become -1; they must stay INF.