Shortest Distance from All Buildings

Hard
925.

Shortest Distance from All Buildings

Shortest Distance from All Buildings is a hard coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google, Meta and MathWorks interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestDistance = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Shortest Distance from All Buildings — Problem & Solution

Shortest Distance from All Buildings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Shortest Distance from All Buildings is a hard coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google, Meta and MathWorks interviews.

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.

Hints for Shortest Distance from All Buildings

  1. Hint 1

    Distances must be measured through empty land, so Manhattan distance is wrong.

  2. Hint 2

    Run a breadth-first search from each building, not from each candidate cell — there are usually far fewer buildings.

  3. Hint 3

    Accumulate, per empty cell, the distance total and how many buildings reached it.

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

  1. For each building, BFS outward through empty cells only.
  2. Add each cell's distance into total[cell] and increment reach[cell].
  3. After all buildings, scan the empty cells whose reach equals the building count.
  4. 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

Java

public static int shortestDistance(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] total = new int[m * n];
    int[] reach = new int[m * n];
    int[] dr = { 1, -1, 0, 0 };
    int[] dc = { 0, 0, 1, -1 };
    int buildings = 0;
    int[] q = new int[m * n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != 1) continue;
            buildings++;
            int[] dist = new int[m * n];
            Arrays.fill(dist, -1);
            dist[i * n + j] = 0;
            int head = 0, tail = 0;
            q[tail++] = i * n + j;
            while (head < tail) {
                int cur = q[head++];
                int r = cur / n, c = cur % n;
                for (int d = 0; d < 4; d++) {
                    int nr = r + dr[d], nc = c + dc[d];
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                    int 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[tail++] = key;
                }
            }
        }
    }
    int best = -1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int k = i * n + j;
            if (grid[i][j] != 0 || reach[k] != buildings) continue;
            if (best < 0 || total[k] < best) best = total[k];
        }
    }
    return best;
}

C++

int shortestDistance(vector<vector<int>>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    vector<int> total(m * n, 0), reach(m * n, 0);
    int dr[4] = { 1, -1, 0, 0 };
    int dc[4] = { 0, 0, 1, -1 };
    int buildings = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != 1) continue;
            buildings++;
            vector<int> dist(m * n, -1);
            dist[i * n + j] = 0;
            vector<int> q;
            q.push_back(i * n + j);
            for (size_t head = 0; head < q.size(); head++) {
                int cur = q[head];
                int r = cur / n, c = cur % n;
                for (int d = 0; d < 4; d++) {
                    int nr = r + dr[d], nc = c + dc[d];
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                    int 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_back(key);
                }
            }
        }
    }
    int best = -1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int k = i * n + j;
            if (grid[i][j] != 0 || reach[k] != buildings) continue;
            if (best < 0 || total[k] < best) best = total[k];
        }
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal