LeetCode 286 · Graphs

Walls and Gates, explained with a picture

Distance from every room to the nearest exit.

MediumGraphs
▶ Watch it step by step

The problem

A grid has walls, gates and empty rooms. Fill each empty room with its distance to the nearest gate (steps up, down, left or right). Rooms that can’t reach a gate stay infinite.

Input:  .WG. / ...W / .W.W / GW..
Output: 3 W 0 1 / 2 2 1 W / 1 W 2 W / 0 W 3 4

Picture it

Picture a building plan with exits (gates). Instead of searching from every room, we start a ripple from all exits at once. The ripple spreads one step per round; the first time it reaches a room, that’s the room’s distance to its nearest exit.

How to recognise it

  • A grid where every empty cell needs its distance to the nearest target (a gate), not to one fixed target.
  • Moves are one step in four directions, and walls block movement, so every step costs the same.
  • There are many sources, and each cell wants the closest one.
  • With grids up to 250 × 250 you cannot start a fresh search for each of 62,500 cells.

Start with brute force

For every empty room, run its own BFS outwards until it reaches a gate, and write the number of steps.

def gates_brute(rooms):
    out = [row[:] for row in rooms]
    for r, c in all_cells(rooms):
        if rooms[r][c] != INF:
            continue
        seen, q = {(r, c)}, deque([(r, c, 0)])
        while q:
            a, b, d = q.popleft()
            if rooms[a][b] == 0:
                out[r][c] = d
                break
            for x, y in nbrs(rooms, a, b):
                if rooms[x][y] != -1 and (x, y) not in seen:
                    seen.add((x, y)); q.append((x, y, d + 1))
    return out

Each room may explore the whole grid, so time is O((R·C)²): around 4 × 10^9 steps for 250 × 250. Space is O(R·C) per search.

From brute force to the idea

  1. Find the waste. The rooms near a gate all search the same neighbourhood, and each search stops when it meets a gate, which is the same event seen from the other side.
  2. Reverse the roles. Instead of each room looking for a gate, let every gate look for rooms. Put all gates in one queue at distance 0.
  3. Spread together. Pop a cell, and give each empty neighbour (INF) the value rooms[r][c] + 1, then queue it. BFS visits cells in order of distance, so the first gate wave to arrive is the nearest one.
  4. The grid is the visited set. A room stops being INF the moment it is filled, so it is never filled twice. Walls are -1 and gates are 0, so neither is ever overwritten.

The key idea: one BFS from all gates at once gives each room the distance to its nearest gate.

The key idea

Multi-source BFS from all gates; first arrival = shortest distance. O(rows × cols).

Python solution

def walls_and_gates(rooms):
    q = deque()
    for r, c in all_cells(rooms):
        if rooms[r][c] == 0:  # a gate
            q.append((r, c))
    while q:  # gates spread together
        r, c = q.popleft()
        d = rooms[r][c] + 1
        for nr, nc in nbrs(rooms, r, c):
            if rooms[nr][nc] == INF:
                rooms[nr][nc] = d
                q.append((nr, nc))

INF = 2**31 - 1  # empty room

def all_cells(g):
    return [(r, c) for r in range(len(g))
            for c in range(len(g[0]))]

def nbrs(g, r, c):  # in-grid neighbours
    R, C = len(g), len(g[0])
    for nr, nc in ((r+1, c), (r-1, c),
                   (r, c+1), (r, c-1)):
        if 0 <= nr < R and 0 <= nc < C:
            yield nr, nc

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO((R·C)²): a BFS per empty roomO(R·C): a visited set per search
Multi-source BFS (shown code)O(R·C): each cell is queued once, with four neighbour checksO(R·C): the queue and the list from all_cells; results are written into the grid

Edge cases

  • No gates: the queue starts empty, so every room stays INF.
  • A room walled off from every gate ([[INF,-1,0]]): stays INF.
  • Only gates or only walls: nothing changes.
  • A gate next to a room ([[0,INF,INF]]): becomes [[0,1,2]].
  • The function returns None and edits rooms in place.
  • Imports and constants: deque must be imported, and INF = 2**31 - 1 is defined after the function in the shown code, which works because it is looked up when the function runs.

Common mistakes

  • Running a BFS from each room instead of from the gates.
  • Running separate BFS passes from each gate in turn, which needs min-merging and is slower.
  • Testing rooms[nr][nc] != -1 instead of == INF, which overwrites gates and earlier answers and can loop forever.
  • Writing a constant 1 instead of the parent's distance plus one.
  • Treating walls as passable.
Your turn: nearest 1 in a matrix

You get a matrix of 0s and 1s with no walls. Return a new matrix where each cell holds its distance to the nearest 1 (an original 1 gets 0). Describe what changes, then write it if you like.

Compare with our answer

It is the same multi-source BFS, with the 1s as the gates. A separate dist matrix filled with -1 serves as the visited marker, so the input stays unchanged.

def nearest_one(m):
    R, C = len(m), len(m[0])
    dist = [[-1] * C for _ in range(R)]
    q = deque()
    for r, c in all_cells(m):
        if m[r][c] == 1:
            dist[r][c] = 0
            q.append((r, c))
    while q:
        r, c = q.popleft()
        for nr, nc in nbrs(m, r, c):
            if dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist

Time O(R·C), space O(R·C). If the matrix has no 1 at all, every distance stays -1.

A strong answer mentions: starting from all the 1s together, a separate distance matrix as the visited set, and the O(R·C) bound.

Check what stuck

1. A city grid marks fire stations and blocked streets. For every open junction you must find the walking distance to the closest station. Which approach fits best?

2. Why is the first value written into a room guaranteed to be its shortest distance?

3. A learner changes d = rooms[r][c] + 1 to d = 1. Which input still gives the right answer?

Score 60% or more and the lesson is marked complete.