Walls And Gates

MEDIUM✓ CHIP-TIMEDLC #286 — FULL STATEMENT ↗

The drill: A grid holds walls (−1), gates (0), and empty rooms (a large placeholder number). Fill every empty room in place with its distance — in steps through open rooms — to the nearest gate; rooms no gate can reach keep their placeholder value.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A grid represents a building's floor plan using three kinds of cells: −1 for an impassable wall, 0 for a gate, and a large placeholder number for an empty room. The task is to overwrite every empty room, in place, with the number of steps to the closest gate.

Movement between rooms only happens up, down, left, or right through open (non-wall) cells — a room that has no path to any gate at all keeps its original placeholder value untouched.

The grid itself is the output — there's no separate return value, just the same array with every reachable empty room replaced by its true distance.

EX 01

rooms = [[0, 2147483647]]

→ [[0, 1]]

ONE GATE, ONE ADJACENT ROOM

EX 02

rooms = [[2147483647, -1], [-1, 0]]

→ [[2147483647, -1], [-1, 0]]

ROOM SEALED OFF BY WALLS FROM THE ONLY GATE

EX 03

rooms = [[0, -1, 2147483647], [2147483647, 2147483647, 2147483647], [2147483647, -1, 0]]

→ [[0, -1, 2], [1, 2, 1], [2, -1, 0]]

TWO GATES SPLITTING THE GRID

grid up to a few hundred cells per side
cells hold exactly one of: −1 (wall), 0 (gate), or the placeholder for empty
movement is 4-directional and blocked entirely by walls
rooms with no path to any gate keep their placeholder value

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Distance-to-nearest-gate from many rooms at once is really distance-from-many-sources at once — what search naturally explores in order of distance, ring by ring?

HINT 2 THE STRUCTURE

Multi-source BFS: start the queue with every gate simultaneously instead of searching once per gate — the first time a room is reached, that's automatically its shortest distance, from whichever gate got there first.

HINT 3 ONE STEP FROM THE ANSWER

Push every gate into the queue at distance 0, then expand outward one ring at a time through non-wall neighbours, writing the ring's distance into any newly-reached empty room and skipping any room that already holds a real number.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE SHARED SWEEPPATTERN · MULTI-SOURCE BFS FROM GATEStwo gates, one wall — INF marks empty rooms

-1

INF

-1

STEP 1

Seed the queue with every gate at once — (0,0) and (2,2) — both at distance 0. Every empty room still reads INF.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/walls-and-gates.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        if not rooms:
            return
        rows, cols = len(rooms), len(rooms[0])
        INF = 2147483647
        queue = collections.deque()
        for r in range(rows):
            for c in range(cols):
                if rooms[r][c] == 0:
                    queue.append((r, c))
        while queue:
            r, c = queue.popleft()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                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))

TIME O(ROWS·COLS)SPACE O(ROWS·COLS)PYTHON · RACE PACE · 18 LN

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        if not rooms:
            return
        rows, cols = len(rooms), len(rooms[0])
        INF = 2147483647
        for r in range(rows):
            for c in range(cols):
                if rooms[r][c] == INF:
                    # BFS outward from this single room to the nearest gate
                    visited = [[False] * cols for _ in range(rows)]
                    visited[r][c] = True
                    queue = collections.deque([(r, c, 0)])
                    found = None
                    while queue:
                        cr, cc, d = queue.popleft()
                        if rooms[cr][cc] == 0:
                            found = d
                            break
                        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                            nr, nc = cr + dr, cc + dc
                            if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc] and rooms[nr][nc] != -1:
                                visited[nr][nc] = True
                                queue.append((nr, nc, d + 1))
                    if found is not None:
                        rooms[r][c] = found

TIME O((ROWS·COLS)²) WORST CASESPACE O(ROWS·COLS)PYTHON · TRAINING PACE · 26 LN

class Solution {
    public void wallsAndGates(int[][] rooms) {
        int rows = rooms.length;
        if (rows == 0) return;
        int cols = rooms[0].length;
        int INF = 2147483647;
        Deque<int[]> queue = new ArrayDeque<>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (rooms[r][c] == 0) queue.add(new int[]{r, c});
            }
        }
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] d : dirs) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && rooms[nr][nc] == INF) {
                    rooms[nr][nc] = rooms[cur[0]][cur[1]] + 1;
                    queue.add(new int[]{nr, nc});
                }
            }
        }
    }
}

TIME O(ROWS·COLS)SPACE O(ROWS·COLS)JAVA · RACE PACE · 25 LN

class Solution {
    public void wallsAndGates(int[][] rooms) {
        int rows = rooms.length;
        if (rows == 0) return;
        int cols = rooms[0].length;
        int INF = 2147483647;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (rooms[r][c] == INF) {
                    boolean[][] visited = new boolean[rows][cols];
                    visited[r][c] = true;
                    Deque<int[]> queue = new ArrayDeque<>();
                    queue.add(new int[]{r, c, 0});
                    Integer found = null;
                    while (!queue.isEmpty()) {
                        int[] cur = queue.poll();
                        if (rooms[cur[0]][cur[1]] == 0) {
                            found = cur[2];
                            break;
                        }
                        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.add(new int[]{nr, nc, cur[2] + 1});
                            }
                        }
                    }
                    if (found != null) {
                        rooms[r][c] = found;
                    }
                }
            }
        }
    }
}

TIME O((ROWS·COLS)²) WORST CASESPACE O(ROWS·COLS)JAVA · TRAINING PACE · 37 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED