LeetCode 317: Shortest Distance from All Buildings

Problem Restatement

We are given an m x n grid.

Each cell has one of three values:

We want to build a house on an empty land cell.

The house must be able to reach every building by moving only up, down, left, and right. Buildings and obstacles cannot be passed through.

Return the minimum total travel distance from one empty land cell to all buildings. If no empty land cell can reach all buildings, return -1. The problem statement defines 0 as passable empty land, 1 as a building, and 2 as an obstacle.

Input and Output

Function shape:

def shortestDistance(grid: list[list[int]]) -> int:
    ...

Examples

Example:

grid = [
    [1, 0, 2, 0, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0],
]

There are three buildings:

(0, 0), (0, 4), (2, 2)

The best empty land cell is:

(1, 2)

Distances:

Total:

3 + 3 + 1 = 7

Output:

7

First Thought: BFS From Every Empty Land

One direct method is:

1. For every empty land cell.
2. Run BFS from that cell.
3. Find the distance to every building.
4. Sum the distances.
5. Keep the minimum valid sum.

This is correct, but it may repeat too much work.

If there are many empty cells, we run many BFS searches.

In the worst case, this costs roughly:

O(E * m * n)

where E is the number of empty cells.

We can do better by reversing the direction.

Key Insight

Instead of BFS from every empty land cell, run BFS from every building.

For each building, BFS computes the shortest distance from that building to every reachable empty land cell.

We maintain two matrices:

After BFS from every building, an empty cell is valid only if:

reach[r][c] == total_buildings

Among those valid cells, choose the smallest dist[r][c].

This works because shortest path distance in an unweighted grid is exactly what BFS computes.

BFS From One Building

For one building at (start_r, start_c):

1. Start BFS from the building.
2. Move only through empty land cells.
3. Track distance by BFS layers.
4. For every reached empty cell:
   • Add the distance to dist[r][c].
   • Increment reach[r][c].

We do not move through buildings or obstacles.

Algorithm

1. Count all buildings.
2. Create dist and reach matrices filled with zero.
3. For each building:
   • Run BFS.
   • Update dist and reach for all reachable empty cells.
4. Scan every cell:
   • It must be empty land.
   • It must be reachable from every building.
   • Use its total distance as a candidate answer.
5. Return the minimum candidate.
6. If no candidate exists, return -1.

Correctness

BFS from a building visits empty cells in increasing distance order. Since every move has cost 1, the first time BFS reaches an empty cell, that distance is the shortest distance from the building to that cell.

The algorithm runs this BFS once for every building. Therefore, for each empty cell, dist[r][c] accumulates the shortest distances from all buildings that can reach it, and reach[r][c] counts how many buildings can reach it.

An empty cell is a valid house location exactly when every building can reach it. This is equivalent to:

reach[r][c] == total_buildings

For each valid empty cell, dist[r][c] is the total travel distance from that cell to all buildings. The algorithm returns the minimum such value.

Therefore, the returned answer is exactly the shortest possible total travel distance. If no empty cell is reachable from all buildings, no valid candidate is found and the algorithm correctly returns -1.

Complexity

Let:

Implementation

from collections import deque

class Solution:
    def shortestDistance(self, grid: list[list[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        dist = [[0] * n for _ in range(m)]
        reach = [[0] * n for _ in range(m)]

        buildings = []

        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1:
                    buildings.append((r, c))

        directions = [
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1),
        ]

        def bfs(start_r: int, start_c: int) -> None:
            queue = deque([(start_r, start_c, 0)])
            visited = [[False] * n for _ in range(m)]
            visited[start_r][start_c] = True

            while queue:
                r, c, d = queue.popleft()

                for dr, dc in directions:
                    nr = r + dr
                    nc = c + dc

                    if not (0 <= nr < m and 0 <= nc < n):
                        continue

                    if visited[nr][nc]:
                        continue

                    if grid[nr][nc] != 0:
                        continue

                    visited[nr][nc] = True
                    dist[nr][nc] += d + 1
                    reach[nr][nc] += 1

                    queue.append((nr, nc, d + 1))

        for r, c in buildings:
            bfs(r, c)

        total_buildings = len(buildings)
        answer = float("inf")

        for r in range(m):
            for c in range(n):
                if grid[r][c] != 0:
                    continue

                if reach[r][c] != total_buildings:
                    continue

                answer = min(answer, dist[r][c])

        if answer == float("inf"):
            return -1

        return answer

Code Explanation

We store the grid dimensions:

m = len(grid)
n = len(grid[0])

dist accumulates total distances.

dist = [[0] * n for _ in range(m)]

reach counts how many buildings can reach each empty cell.

reach = [[0] * n for _ in range(m)]

Then we collect all buildings.

buildings = []

for r in range(m):
    for c in range(n):
        if grid[r][c] == 1:
            buildings.append((r, c))

The BFS starts from one building.

queue = deque([(start_r, start_c, 0)])

Each queue entry stores row, column, and distance from the building.

Each BFS needs its own visited matrix.

visited = [[False] * n for _ in range(m)]

When BFS sees a neighbor, it first checks boundaries.

if not (0 <= nr < m and 0 <= nc < n):
    continue

Then it rejects already visited cells.

if visited[nr][nc]:
    continue

Then it rejects buildings and obstacles.

if grid[nr][nc] != 0:
    continue

Only empty land cells can be visited.

For a valid empty cell, update the distance and reach count.

dist[nr][nc] += d + 1
reach[nr][nc] += 1

After running BFS from every building, scan all empty cells.

if reach[r][c] != total_buildings:
    continue

This keeps only cells reachable from every building.

Then choose the smallest total distance.

answer = min(answer, dist[r][c])

If no valid empty land was found, return -1.

Testing

def run_tests():
    s = Solution()

    assert s.shortestDistance([
        [1, 0, 2, 0, 1],
        [0, 0, 0, 0, 0],
        [0, 0, 1, 0, 0],
    ]) == 7

    assert s.shortestDistance([
        [1, 0],
    ]) == 1

    assert s.shortestDistance([
        [1],
    ]) == -1

    assert s.shortestDistance([
        [1, 2, 0],
    ]) == -1

    assert s.shortestDistance([
        [1, 0, 1],
    ]) == 2

    assert s.shortestDistance([
        [1, 0, 0],
        [2, 2, 0],
        [1, 0, 0],
    ]) == 6

    print("all tests passed")

run_tests()

Test meaning: