Walls and Gates

1. Problem & Core Objective

You are given an m × n grid where each cell is one of:

• -1 — a wall or obstacle
• 0 — a gate
• INF (2^31 − 1) — an empty room

Fill each empty room with the distance to its nearest gate. If no gate can reach it, leave it as INF.

INF  -1   0  INF          3  -1   0   1
INF INF INF  -1     →     2   2   1  -1
INF  -1 INF  -1           1  -1   2  -1
  0  -1 INF INF           0  -1   3   4

Constraints: 1 <= m, n <= 250 · movement is four-directional

What's actually being tested: multi-source BFS. Running a BFS from every room is O((m·n)²); seeding the queue with all gates at once computes every distance in a single O(m·n) sweep. It's the most valuable single idea in this section and it reappears in question 5.

2. First-Principles Thought Process

The wrong direction first

The natural reading is "for each room, find the nearest gate" — which means a BFS from each room. With up to 62,500 cells each running a 62,500-cell BFS, that's 4 × 10^9 operations.

Reverse it

Instead ask: from each gate, how far does it reach? Now the sources are gates, which are typically far fewer than rooms.

But running a separate BFS per gate and taking the minimum is still O(gates · m · n).

Seed them all simultaneously

Put every gate in the queue before starting. All of them sit at distance 0 at the same time, so the BFS expands outward from all gates in lockstep.

Why the first arrival is already the minimum

BFS visits cells in non-decreasing order of distance from the seed set. So when a cell is first dequeued — or first reached — that distance is its minimum over all gates.

No cell ever needs updating, which is why a visited cell can simply be skipped rather than compared. That's the property that makes it a single sweep rather than a relaxation algorithm like Dijkstra.

The elegant visited marker

An empty room is INF; once assigned a real distance it is no longer INF. So:

if (grid[nr][nc] != INF) continue;      // wall, gate, or already assigned

One condition covers all three cases — walls are -1, gates are 0, assigned rooms are finite. No separate visited array.

Same trick as sinking cells in question 2, and it works for the same reason: the three cases genuinely warrant identical treatment.

3. Solution Paths

Approach 1 — BFS from every room (brute force)

public void wallsAndGates(int[][] rooms) {
    int m = rooms.length, n = rooms[0].length;
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (rooms[r][c] == Integer.MAX_VALUE)
                rooms[r][c] = bfsToNearestGate(rooms, r, c);     // a full BFS per room
}

• Time O((m · n)²) · Space O(m · n) per BFS

Counter-questions on this approach

⭐ "How bad is that at these constraints?"

250 × 250 = 62,500 cells, and a BFS from each can visit all 62,500 — about 4 × 10^9 operations. Far too slow.

And most of that work is repeated: adjacent rooms explore nearly identical regions and rediscover the same distances independently.

⭐ "Reversing to 'BFS from each gate' — does that fix it?"

It helps when gates are few, but the bound is O(gates · m · n), and a grid could be mostly gates. It also requires taking a minimum across runs, so every cell is written repeatedly.

The real fix is doing one BFS with all gates seeded, which is O(m · n) regardless of how many gates there are.

"Is there any case where per-room BFS is acceptable?"

If there were exactly one room to answer for — a single query rather than filling the grid. Then one BFS is O(m·n) and seeding everything would be wasted. The multi-source version pays off precisely because every cell needs an answer.

Approach 2 — Multi-source BFS (optimal)

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

public void wallsAndGates(int[][] rooms) {
    int m = rooms.length, n = rooms[0].length;
    Queue<int[]> q = new ArrayDeque<>();

    for (int r = 0; r < m; r++)                       // seed EVERY gate
        for (int c = 0; c < n; c++)
            if (rooms[r][c] == 0) q.offer(new int[]{r, c});

    while (!q.isEmpty()) {
        int[] cell = q.poll();
        int r = cell[0], c = cell[1];

        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if (rooms[nr][nc] != INF) continue;        // wall, gate, or already assigned

            rooms[nr][nc] = rooms[r][c] + 1;           // assign on discovery
            q.offer(new int[]{nr, nc});
        }
    }
}

Trace — the example grid, first two rounds:

Every cell is written once, at its true minimum distance.

• Time O(m · n) · Space O(m · n) queue worst case

Counter-questions on this approach

⭐ "Why does seeding all gates give the NEAREST gate rather than an arbitrary one?"

Because BFS expands strictly in order of distance from the seed set. Every gate is at distance 0 simultaneously, so the wavefront at step k is exactly the set of cells whose nearest gate is k steps away.

A cell is therefore first reached at its minimum distance over all gates. No later path can be shorter, which is why I never have to compare or update — first write wins, and it's already optimal.

⭐ "Why assign the distance on discovery rather than when the cell is dequeued?"

Two reasons. It doubles as the visited marker — an assigned cell is no longer INF, so the guard rejects it. And it prevents the same cell being enqueued from several neighbours before being processed, which would inflate the queue with duplicates.

Marking on enqueue is the standard BFS discipline; here it also is the answer being written.

⭐ "Why does one guard cover walls, gates, and assigned rooms?"

Because only INF cells need processing. Walls are -1, gates are 0, and an assigned room holds a finite distance — none are INF, so != INF rejects all three.

Collapsing them is safe because all three warrant the same treatment: skip. With a separate visited array they'd be independent tests.

"Could rooms[r][c] + 1 overflow?"

Only if rooms[r][c] were INF = Integer.MAX_VALUE, which would wrap to MIN_VALUE. But a cell is only dequeued after being assigned a real distance — or being a seeded gate at 0 — so the value is always finite and small.

Worth checking rather than assuming, because MAX_VALUE + 1 is exactly the kind of thing that produces a plausible-looking negative distance.

"What happens to rooms no gate can reach?"

They stay INF, which is the required behaviour. The BFS simply never reaches them — walls block every path — so they're never written.

"How large can the queue get?"

Bounded by the frontier, but in the worst case — a grid that is all gates — every cell is seeded at once, so O(m · n). At 62,500 entries that's fine.

Comparison

4. Why the Optimal Wins

Per-room BFS repeats nearly identical explorations for adjacent rooms. Per-gate BFS repeats the grid once per gate and overwrites cells as better distances appear.

Multi-source BFS does one sweep in which every cell is written exactly once, already at its minimum. The saving isn't a clever data structure — it's asking the question from the right end, and then asking it about all sources at once.

The framing worth keeping:

When you want the distance to the NEAREST of many sources, seed the BFS queue with all of them. They all sit at distance 0, the wavefront expands from all at once, and the first time a cell is reached is already its minimum.

Question 5 is the same technique with a different story attached.

5. Java Prerequisites

Multi-source seeding

for every source cell: q.offer(new int[]{r, c});     // BEFORE the while loop
while (!q.isEmpty()) { ... }

Assign on discovery, not on dequeue

rooms[nr][nc] = rooms[r][c] + 1;
q.offer(new int[]{nr, nc});

The assignment is both the answer and the visited marker.

Integer.MAX_VALUE as INF — note MAX_VALUE + 1 overflows to MIN_VALUE. Safe here only because assigned cells always hold small finite values.

ArrayDeque<int[]> for the queue — offer/poll, no nulls.

6. Interview Communication Guide

Clarifying questions: Modify the grid in place (yes — the signature returns void)? Are diagonals allowed (no)? What should unreachable rooms hold (stay INF)? Can there be zero gates (yes — then nothing changes)?

The pitch

"The natural reading is 'for each room, find the nearest gate', which means a BFS per room — O((m·n)²), about 4 × 10^9 here. Far too slow, and most of the work is repeated between adjacent rooms.

Reversing it to 'BFS from each gate' helps but is still O(gates · m·n).

The fix is multi-source BFS: seed the queue with every gate before starting. They all sit at distance 0 simultaneously, so the wavefront expands outward from all gates at once.

That's correct because BFS visits cells in non-decreasing order of distance from the seed set. So the first time a cell is reached, that distance is already its minimum over all gates — no cell ever needs updating, which is why a visited cell can just be skipped rather than compared.

I assign the distance on discovery rather than on dequeue. That serves two purposes: it's the answer, and it's the visited marker, since an assigned room is no longer INF. It also stops the same cell being enqueued from several neighbours.

That gives one elegant guard — if (rooms[nr][nc] != INF) continue; — which covers walls, gates, and already-assigned rooms in a single test, because none of them are INF.

O(m·n) time, every cell written exactly once. Unreachable rooms stay INF automatically, since the BFS never gets to them."

Edge cases to volunteer:

Name the no-gates case. The queue starts empty and the loop never executes, leaving the grid untouched — correct, but only if you didn't assume at least one source exists.

7. Follow-Up Questions — Modified Constraints

⭐ "Rotting Oranges — same technique?"

Yes, question 5. Rotten oranges are the sources, fresh ones are the rooms, and the answer is the number of BFS levels rather than per-cell distances. Recognising them as the same algorithm with different framing is the point of having both.

⭐ "What if moving through different cells cost different amounts?"

BFS breaks, because it assumes every edge costs 1 — the wavefront is only distance-ordered under uniform cost. You'd need Dijkstra with a priority queue, at O(m·n log(m·n)). Multi-source works there too: seed the heap with all sources at distance 0.

"Return the distance for a single room rather than filling the grid."

Then one BFS from that room is O(m·n) and seeding all gates is wasted work. The multi-source version pays off precisely because every cell needs an answer — worth saying, since it inverts the advice.

"What if gates could be added or removed dynamically?"

Recomputing is O(m·n) per change. Adding a gate can be done incrementally — BFS outward from it, stopping wherever the existing distance is already smaller. Removing one is much harder, since you'd have to recompute every cell that relied on it.

"Find the room that is FARTHEST from any gate."

Same sweep, then take the maximum finite value. One extra pass, or track the maximum as cells are assigned.

"What if the grid were 10^4 × 10^4?"

10^8 cells — the queue of int[] objects would be enormous. Encode coordinates as a single int (r * n + c) in an ArrayDeque<Integer>, or better use an int[] ring buffer, to avoid allocating 100 million small arrays.