Difficulty: MediumGraphs

Walls and Gates

Problem in Plain English

Rooms hold walls, gates, and empty cells marked with a huge INF value. Fill every empty cell with its distance to the nearest gate, leaving cells no gate can reach as INF.

Problem Statement

You are given an m x n grid rooms holding three possible values: -1 for a wall, 0 for a gate, and 2147483647 (INF) for an empty room. Fill each empty room with its distance to the nearest gate.

If no gate can reach an empty room, leave it as INF. Modify the grid in place and do not return anything.

Constraints

m == rooms.length
n == rooms[i].length
1 <= m, n <= 250
rooms[i][j] is -1, 0, or 2147483647.

Examples

Example 1

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Cell (0,0) is three steps from gate (3,0) through (2,0) and (1,0). Cell (3,3) is four steps from gate (0,2) through (1,2), (2,2), and (3,2); the bottom gate needs six steps because walls force a detour. Gates and walls retain their original values.

Example 2

Input: rooms = [[-1]]
Output: [[-1]]

The single cell is a wall, so nothing changes.

Example 3

Input: rooms = [[0,2147483647,-1,2147483647],[2147483647,2147483647,-1,2147483647]]
Output: [[0,1,-1,2147483647],[1,2,-1,2147483647]]

The gate reaches the left component at distances 1, 1, and 2. The full wall column separates both right-hand rooms from the gate, so those rooms remain INF even though they are close geometrically.

Example 4

Input: rooms = [[0,2147483647,2147483647,2147483647,0]]
Output: [[0,1,2,1,0]]

Two gates approach the middle room from opposite ends. Its nearest distance is 2, regardless of which wave arrives first; the room next to the right gate gets 1 rather than 3 from the left gate.

Intuition

Each legal up, down, left or right move costs one step, so rooms and gates form an unweighted graph with walls removed. Breadth-first search visits positions in increasing distance. In Example 1, the bottom gate reaches (0,0) in three steps, while the top gate reaches (3,3) in four. Searching separately from each room works, but starting one queue at every gate shares those corridor walks. A room first reached by any gate has already found its nearest gate; unreachable rooms never change.

Approaches

BFS From Every Room

Solution Details

Reveal BFS From Every Room: intuition, complexity, and code

Intuition

Treat each empty room as its own problem: launch a search from it and stop at the first gate reached. The first gate found is the nearest one, but neighbouring rooms re-walk the same corridors to the same gates, which is the repeated work the optimal approach removes.

Step-by-Step Logic

Scan the grid in row order, launching a new BFS only from a room still equal to INF. Keep gates and walls unchanged. Example 1 starts at (0,0).
For each search, put (start row, start column, 0) in a FIFO queue and mark that coordinate seen. Remove the next triple; if its grid value is zero, return its carried distance.
Otherwise enqueue unseen in-bounds non-wall neighbours with distance one greater, marking them before enqueueing. Use down, up, right, left order. From (0,0), the search eventually dequeues gate (3,0) at distance 3.
Write the returned distance into the start room, or INF if the queue drains. Later searches must cross rooms already given finite distances, since they are still corridors. Repeat for every original empty room; (3,3) returns 4.
After the last room, Example 1 is [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]. Return no value; retain the caller's grid and row objects.

Why It Works

For each original empty room, a fresh visited structure and FIFO queue explore every reachable non-wall position at most once, in nondecreasing path length. Thus the first dequeued gate has the minimum distance; if the queue empties, no gate is reachable. Distances already written for earlier rooms remain traversable: only walls block movement, and only zero identifies a gate. Writing a positive distance neither creates a gate nor changes connectivity, so subsequent searches remain correct. Walls and gates are skipped by the outer loop and remain unchanged.

Dry Run

BFS From Every Room: variable states at each step
Start (r,c)	Dequeued (r,c,d)	New seen/enqueued triples	Pending queue after	Write / seen count
(0,0) initialize	-	[(0,0,0)]	[(0,0,0)]	seen = 1
(0,0)	(0,0,0)	[(1,0,1)]	[(1,0,1)]	no write; seen = 2
(0,0)	(1,0,1)	[(2,0,2),(1,1,2)]	[(2,0,2),(1,1,2)]	no write; seen = 4
(0,0)	(2,0,2)	[(3,0,3)]	[(1,1,2),(3,0,3)]	no write; seen = 5
(0,0)	(1,1,2)	[(1,2,3)]	[(3,0,3),(1,2,3)]	no write; seen = 6
(0,0)	(3,0,3) gate	none	[(1,2,3)] (discard)	rooms[0][0] = 3; seen = 6
(0,3) initialize	-	[(0,3,0)]	[(0,3,0)]	seen = 1
(0,3)	(0,3,0)	[(0,2,1)]	[(0,2,1)]	no write; seen = 2
(0,3)	(0,2,1) gate	none	[] (discard)	rooms[0][3] = 1; seen = 2
(1,0) initialize	-	[(1,0,0)]	[(1,0,0)]	seen = 1
(1,0)	(1,0,0)	[(2,0,1),(0,0,1),(1,1,1)]	[(2,0,1),(0,0,1),(1,1,1)]	no write; seen = 4
(1,0)	(2,0,1)	[(3,0,2)]	[(0,0,1),(1,1,1),(3,0,2)]	no write; seen = 5
(1,0)	(0,0,1)	[]	[(1,1,1),(3,0,2)]	no write; seen = 5
(1,0)	(1,1,1)	[(1,2,2)]	[(3,0,2),(1,2,2)]	no write; seen = 6
(1,0)	(3,0,2) gate	none	[(1,2,2)] (discard)	rooms[1][0] = 2; seen = 6
(1,1) initialize	-	[(1,1,0)]	[(1,1,0)]	seen = 1
(1,1)	(1,1,0)	[(1,2,1),(1,0,1)]	[(1,2,1),(1,0,1)]	no write; seen = 3
(1,1)	(1,2,1)	[(2,2,2),(0,2,2)]	[(1,0,1),(2,2,2),(0,2,2)]	no write; seen = 5
(1,1)	(1,0,1)	[(2,0,2),(0,0,2)]	[(2,2,2),(0,2,2),(2,0,2),(0,0,2)]	no write; seen = 7
(1,1)	(2,2,2)	[(3,2,3)]	[(0,2,2),(2,0,2),(0,0,2),(3,2,3)]	no write; seen = 8
(1,1)	(0,2,2) gate	none	[(2,0,2),(0,0,2),(3,2,3)] (discard)	rooms[1][1] = 2; seen = 8
(1,2) initialize	-	[(1,2,0)]	[(1,2,0)]	seen = 1
(1,2)	(1,2,0)	[(2,2,1),(0,2,1),(1,1,1)]	[(2,2,1),(0,2,1),(1,1,1)]	no write; seen = 4
(1,2)	(2,2,1)	[(3,2,2)]	[(0,2,1),(1,1,1),(3,2,2)]	no write; seen = 5
(1,2)	(0,2,1) gate	none	[(1,1,1),(3,2,2)] (discard)	rooms[1][2] = 1; seen = 5
(2,0) initialize	-	[(2,0,0)]	[(2,0,0)]	seen = 1
(2,0)	(2,0,0)	[(3,0,1),(1,0,1)]	[(3,0,1),(1,0,1)]	no write; seen = 3
(2,0)	(3,0,1) gate	none	[(1,0,1)] (discard)	rooms[2][0] = 1; seen = 3
(2,2) initialize	-	[(2,2,0)]	[(2,2,0)]	seen = 1
(2,2)	(2,2,0)	[(3,2,1),(1,2,1)]	[(3,2,1),(1,2,1)]	no write; seen = 3
(2,2)	(3,2,1)	[(3,3,2)]	[(1,2,1),(3,3,2)]	no write; seen = 4
(2,2)	(1,2,1)	[(0,2,2),(1,1,2)]	[(3,3,2),(0,2,2),(1,1,2)]	no write; seen = 6
(2,2)	(3,3,2)	[]	[(0,2,2),(1,1,2)]	no write; seen = 6
(2,2)	(0,2,2) gate	none	[(1,1,2)] (discard)	rooms[2][2] = 2; seen = 6
(3,2) initialize	-	[(3,2,0)]	[(3,2,0)]	seen = 1
(3,2)	(3,2,0)	[(2,2,1),(3,3,1)]	[(2,2,1),(3,3,1)]	no write; seen = 3
(3,2)	(2,2,1)	[(1,2,2)]	[(3,3,1),(1,2,2)]	no write; seen = 4
(3,2)	(3,3,1)	[]	[(1,2,2)]	no write; seen = 4
(3,2)	(1,2,2)	[(0,2,3),(1,1,3)]	[(0,2,3),(1,1,3)]	no write; seen = 6
(3,2)	(0,2,3) gate	none	[(1,1,3)] (discard)	rooms[3][2] = 3; seen = 6
(3,3) initialize	-	[(3,3,0)]	[(3,3,0)]	seen = 1
(3,3)	(3,3,0)	[(3,2,1)]	[(3,2,1)]	no write; seen = 2
(3,3)	(3,2,1)	[(2,2,2)]	[(2,2,2)]	no write; seen = 3
(3,3)	(2,2,2)	[(1,2,3)]	[(1,2,3)]	no write; seen = 4
(3,3)	(1,2,3)	[(0,2,4),(1,1,4)]	[(0,2,4),(1,1,4)]	no write; seen = 6
(3,3)	(0,2,4) gate	none	[(1,1,4)] (discard)	rooms[3][3] = 4; seen = 6
Finished row scan	-	-	[]	[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Complexity Analysis

Time Complexity

O((mn)^2)

Space Complexity

O(mn)

There are at most mn original empty rooms, each searching up to mn cells and checking four neighbours per cell. Java and JavaScript also allocate and initialize a fresh mn-cell seen grid for each search; Python creates a fresh visited set whose size grows with discovery. Only one search is active, so its visited storage and queue need O(mn) auxiliary space; JavaScript retains consumed queue entries until that search returns. Cumulative allocations can total O((mn)^2), but peak live auxiliary storage is O(mn). The caller-owned grid is the output, with no separate output copy. The brute force is a teaching baseline and can be too slow at the maximum bounds.

Code

Solution.java

1import java.util.ArrayDeque;2import java.util.Queue;3
4class Solution {5    public void wallsAndGates(int[][] rooms) {6        int m = rooms.length;7        int n = rooms[0].length;8        for (int r = 0; r < m; r++) {9            for (int c = 0; c < n; c++) {10                if (rooms[r][c] == Integer.MAX_VALUE) {11                    rooms[r][c] = nearestGate(rooms, r, c);12                }13            }14        }15    }16
17    private int nearestGate(int[][] rooms, int sr, int sc) {18        int m = rooms.length;19        int n = rooms[0].length;20        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};21        Queue<int[]> queue = new ArrayDeque<>();22        boolean[][] seen = new boolean[m][n];23        queue.offer(new int[]{sr, sc, 0});24        seen[sr][sc] = true;25        while (!queue.isEmpty()) {26            int[] curr = queue.poll();27            int r = curr[0];28            int c = curr[1];29            int d = curr[2];30            // FIFO explores shortest paths first; only zero is a gate.31            if (rooms[r][c] == 0) {32                return d;33            }34            for (int[] dir : dirs) {35                int nr = r + dir[0];36                int nc = c + dir[1];37                // Written positive distances remain corridors; bounds precede indexing.38                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !seen[nr][nc] && rooms[nr][nc] != -1) {39                    seen[nr][nc] = true;40                    queue.offer(new int[]{nr, nc, d + 1});41                }42            }43        }44        // No reachable gate: preserve the sentinel without arithmetic on INF.45        return Integer.MAX_VALUE;46    }47}

Hints

Hint 1

Searching outward from every empty room re-walks the same corridors to the same gates, so look for one search that serves all rooms.

Hint 2

Waves leaving every gate at the same speed arrive at each room along the shortest route, which suggests seeding the search at all gates at once.

Hint 3

Stamp a room only while it still holds INF: the first arrival is the nearest gate, and later waves must not overwrite it.

Edge Cases

A grid with no gates at all, where every empty room correctly keeps 2147483647.
A grid with no empty rooms, where the sweep finds nothing to stamp and changes nothing.
An empty room sealed behind walls, which no wave reaches and which keeps 2147483647.
Two gates equally near a room produce the same distance; queue ordering must not change the output.
A single-row or single-column corridor exercises all boundary checks. The farthest finite distance is bounded by the number of non-wall cells minus one.

Common Mistakes and Interview Tips

Searching from each empty room instead of once from all gates, which repeats corridor walks and times out on large grids.
Re-stamping rooms that already hold a distance, letting a slower wave overwrite the shortest arrival.
Walking through walls by checking only bounds and forgetting the -1 guard.
In a BFS from each room, treating previously filled positive rooms as blocked disconnects corridors needed by later searches.
Adding one to INF can overflow Java int. Only expand gates or rooms already assigned a finite distance.
Interview tip: in-place output does not mean constant auxiliary space; the queue can still need O(mn). The input contract is an original grid of -1, 0, and INF values.

Key Takeaway

When every target needs its distance to the nearest of many sources, start one joint search at all sources and stamp each target on first arrival.