Shortest Distance from All Buildings

Shortest Distance from All Buildings

What is this problem about?

The Shortest Distance from All Buildings interview question gives you a grid containing empty land (0), buildings (1), and obstacles (2). You want to place a new building on an empty cell that minimizes the total walking distance to all existing buildings. Walking distance is the Manhattan distance (4-directional). Empty land must be reachable from all buildings. Return the minimum total distance, or -1 if no valid placement exists.

Why is this asked in interviews?

Apple, Microsoft, Meta, Amazon, Google, Bloomberg, and Waymo ask this HARD problem because it tests multi-source BFS on a grid — a core pattern in location optimization, warehouse placement, and urban planning algorithms. The naive approach (BFS from each empty cell to all buildings) is O((m×n)^2); the efficient approach (BFS from each building to all reachable empty cells) is O(buildings × m × n) — typically much faster when buildings are sparse.

Algorithmic pattern used

The pattern is BFS from every building. For each building, run BFS to compute the distance from that building to every reachable empty cell. Accumulate the total distance at each empty cell across all BFS runs. Also track how many buildings can reach each cell. The answer is the minimum total distance among cells reachable from ALL buildings. To avoid re-checking obstacles, decrement the "empty" marker by 1 after each BFS sweep — only cells still matching the current "empty" marker participate in the next BFS.

Example explanation

Grid:

1 0 2 0 1
0 0 0 0 0
0 0 1 0 0

Buildings at (0,0), (0,4), (2,2).

BFS from each building to all reachable cells. Accumulate distances. The cell with minimum total distance that is reachable from all 3 buildings is the answer.

Cell (1,2): distance from (0,0)=3, from (0,4)=3, from (2,2)=1. Total = 7 (minimum).

Common mistakes candidates make

• Running BFS from each empty cell (O((mn)^2)) instead of from each building — buildings are usually far fewer than empty cells.
• Not checking that a candidate cell can reach ALL buildings — cells unreachable from some building are invalid.
• Not handling obstacles during BFS expansion — obstacle cells (value 2) cannot be traversed.
• Off-by-one in distance tracking when using the decremented "empty" marker trick.

Interview preparation tip

For the Shortest Distance from All Buildings coding problem, the BFS matrix interview pattern with multi-source distance accumulation is the key. The decremented-marker trick (reducing the empty land value after each BFS pass) efficiently filters out cells that aren't reachable from all buildings in O(1). Google and Bloomberg interviewers ask about the time complexity tradeoff between BFS-from-empty vs BFS-from-buildings — know both complexities and articulate when each is preferable. Practice the "accumulate distance across multiple BFS sweeps" pattern.