Shortest Distance from All Buildings — Hard Problem & Solution

A grid holds 0 for empty land, 1 for a building and 2 for an obstacle.

Difficulty: Hard
Topics: Arrays, Matrix, Breadth-First Search
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A grid holds 0 for empty land, 1 for a building and 2 for an obstacle. You want to build a house on an empty cell so that the total travel distance to all buildings is as small as possible. Travel is 4-directional and passes only through empty land.

Return that smallest total distance, or -1 if no empty cell can reach every building.

Example 1

Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7
Explanation: The cell `(1,2)` is 3 + 3 + 1 away from the three buildings.

Example 2

Input: grid = [[1,0]]
Output: 1

Example 3

Input: grid = [[1]]
Output: -1
Explanation: There is no empty cell at all.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is 0, 1 or 2
There is at least one building.

How to solve Shortest Distance from All Buildings

Sweep once per building: a BFS from a building labels every empty cell it can reach with its distance. Adding those into per-cell totals, plus a count of how many buildings got there, answers every candidate at once.

Approach

For each building, BFS outward through empty cells only.
Add each cell's distance into total[cell] and increment reach[cell].
After all buildings, scan the empty cells whose reach equals the building count.
Return the smallest total among them, or -1 if there is none.

Why it works

Running the BFS from the buildings rather than from each candidate cell is what keeps it affordable: buildings · m · n instead of emptyCells · m · n, and a grid is usually mostly empty. The reach counter is essential — a cell that some building cannot reach is not a valid site no matter how small its partial total is.

Complexity

Time — O(buildings · m · n)
Space — O(m · n)

Pitfalls

A cell reachable by only some buildings must be rejected, not scored.
The BFS walks through 0 cells only; a building is never a through-route.
Each building needs its own visited grid, or later searches stop early.

Reference solution

Python

from typing import List
from collections import deque

def shortestDistance(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    total = [0] * (m * n)
    reach = [0] * (m * n)
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    buildings = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] != 1:
                continue
            buildings += 1
            dist = [-1] * (m * n)
            dist[i * n + j] = 0
            q = deque([(i, j)])
            while q:
                r, c = q.popleft()
                for di, dj in dirs:
                    nr, nc = r + di, c + dj
                    if not (0 <= nr < m and 0 <= nc < n):
                        continue
                    key = nr * n + nc
                    if dist[key] >= 0 or grid[nr][nc] != 0:
                        continue
                    dist[key] = dist[r * n + c] + 1
                    total[key] += dist[key]
                    reach[key] += 1
                    q.append((nr, nc))
    best = -1
    for i in range(m):
        for j in range(n):
            key = i * n + j
            if grid[i][j] != 0 or reach[key] != buildings:
                continue
            if best < 0 or total[key] < best:
                best = total[key]
    return best

JavaScript

var shortestDistance = function(grid) {
    var m = grid.length, n = grid[0].length, i, j, d;
    var total = [], reach = [];
    for (i = 0; i < m * n; i++) { total.push(0); reach.push(0); }
    var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    var buildings = 0;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            if (grid[i][j] !== 1) continue;
            buildings++;
            var dist = [];
            for (var t = 0; t < m * n; t++) dist.push(-1);
            dist[i * n + j] = 0;
            var q = [i * n + j];
            var head = 0;
            while (head < q.length) {
                var cur = q[head++];
                var r = Math.floor(cur / n), c = cur % n;
                for (d = 0; d < 4; d++) {
                    var nr = r + dr[d], nc = c + dc[d];
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                    var key = nr * n + nc;
                    if (dist[key] >= 0 || grid[nr][nc] !== 0) continue;
                    dist[key] = dist[cur] + 1;
                    total[key] += dist[key];
                    reach[key]++;
                    q.push(key);
                }
            }
        }
    }
    var best = -1;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            var k = i * n + j;
            if (grid[i][j] !== 0 || reach[k] !== buildings) continue;
            if (best < 0 || total[k] < best) best = total[k];
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue