Shortest Distance from All Buildings

Shortest Distance from All Buildings is a grid-BFS classic. The trick is not one clever search — it is running a plain BFS once per building and letting the distances pile up in shared scratch arrays.

The slow way first

You might try the reverse: stand on each empty cell and BFS out to find every building. That is correct, but wasteful — most cells are empty, so you would launch a search from nearly every cell in the grid. With E empty cells and a full grid, that is roughly O(E · m · n) searches, and the empty cells usually dominate.

The question to ask: which thing is there fewer of? Buildings. So flip the direction — search from the buildings instead of from the empty cells.

The idea: one BFS per building, accumulate

Run a BFS rooted at each building. As that wave spreads, add the current distance into a total[r][c] array for every empty cell it touches, and bump a reach[r][c] counter so we know how many buildings have reached that cell. After all buildings have run, the answer is the smallest total among cells whose reach equals the building count — only those are reachable by all buildings.

The key insight: because BFS visits cells in distance order, the first time a wave reaches a cell is the shortest distance from that building — no relaxation needed.

Walk through it

Step through the animation. Building #1 (top-left) sends out a wave; each ring writes 1, 2, then 3 into the land cells, flowing around the wall in the centre. Then building #2 (bottom-right) runs its own wave, adding its distances on top. After both, every land cell holds the combined total and has been reached twice. The smallest such total is the answer.

Pseudocode

total[r][c] = 0 and reach[r][c] = 0 for every cell
buildings = 0
for each cell (r, c):
    if grid[r][c] is a building:
        buildings += 1
        BFS from (r, c):
            when the wave reaches an empty cell at distance d:
                total[cell] += d
                reach[cell] += 1
best = infinity
for each empty cell with reach == buildings:
    best = min(best, total[cell])
return best if it changed else -1

The Python solution

def shortest_distance(grid):
    rows, cols = len(grid), len(grid[0])
    total = [[0] * cols for _ in grid]
    reach = [[0] * cols for _ in grid]
    buildings = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                buildings += 1
                bfs(grid, r, c, total, reach)
    best = float("inf")
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 0 and reach[r][c] == buildings:
                best = min(best, total[r][c])
    return best if best < float("inf") else -1

• total and reach are grids the same shape as the input, shared across every BFS.
• We count buildings so we know the target reach value a cell must hit to be a candidate.
• Line 10 runs one BFS per building; inside it, each empty cell reached at distance d does total += d and reach += 1 (and marks itself visited for that building only).
• Lines 14–16 are the final scan: a land cell qualifies only when reach == buildings, and we keep the smallest total among those.
• If no cell was reachable by all buildings, best stays infinite and we return -1.

Complexity

The two scratch grids cost O(m · n) space. Searching from the buildings wins because buildings are typically the rarer cell type, so B is much smaller than E.

When this pattern shows up

Practice