Skip to main content
Talentd

Shortest Distance from All Buildings - Solution & Explanation

HardPremiumFree on FleetCodeArrayBreadth-First SearchMatrix6 min readAsked at: Amazon, Microsoft, Apple +12
Practice this problem

Problem Statement

You are given an m x n grid grid of values 0, 1, or 2, where:

  • each 0 marks an empty land that you can pass by freely,
  • each 1 marks a building that you cannot pass through, and
  • each 2 marks an obstacle that you cannot pass through.

You want to build a house on an empty land that reaches all buildings in the shortest total travel distance. You can only move up, down, left, and right.

Return the shortest travel distance for such a house. If it is not possible to build such a house according to the above rules, return -1.

The total travel distance is the sum of the distances between the houses of the friends and the meeting point.

 

Example 1:

Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7
Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2).
The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal.
So return 7.

Example 2:

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

Example 3:

Input: grid = [[1]]
Output: -1

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] is either 0, 1, or 2.
  • There will be at least one building in the grid.

Approach Overview

Problem Overview: You are given a grid with buildings (1), empty land (0), and obstacles (2). The goal is to choose an empty cell where building a house results in the minimum total travel distance to every building. Movement is allowed in four directions, and obstacles block paths.

Approach 1: BFS from Every Empty Land (Brute Force) (Time: O((mn)^2), Space: O(mn))

Iterate through the grid and treat every empty cell as a potential house location. For each empty cell, run a Breadth-First Search to compute the distance to every building. BFS guarantees the shortest path in an unweighted grid. While exploring neighbors, accumulate the distance whenever a building is reached. If all buildings are reachable, update the global minimum.

This approach works because BFS explores the grid level by level, ensuring shortest path distances. The drawback is repeated traversal of the entire grid for every empty cell. In dense grids with many empty cells, this becomes expensive since each BFS costs O(mn).

Approach 2: BFS from Each Building (Optimal) (Time: O(kmn), Space: O(mn))

A more efficient strategy reverses the search direction. Instead of starting BFS from empty land, start BFS from each building. During traversal, update two matrices: one that accumulates total distance to each empty cell and another that counts how many buildings can reach that cell.

For every building, perform BFS across the matrix. When visiting an empty cell, add the current distance to its cumulative sum and increment its reachable-building counter. After processing all buildings, scan the grid and select the empty cell whose reachable-building count equals the total number of buildings and whose distance sum is minimal.

This works because BFS from each building computes shortest distances once per building rather than once per empty cell. The grid is traversed k times where k is the number of buildings, producing a total complexity of O(kmn). Distance aggregation avoids recomputation and keeps the solution scalable even for larger grids.

Recommended for interviews: The BFS-from-buildings approach is what interviewers expect. It demonstrates strong understanding of array grid traversal and BFS optimization. Mentioning the brute force solution first shows problem exploration, while transitioning to the building-based BFS shows algorithmic improvement and awareness of time complexity tradeoffs.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS from Every Empty LandO((mn)^2)O(mn)Useful for understanding the problem or when the grid has very few empty cells.
BFS from Each Building (Distance Accumulation)O(kmn)O(mn)General optimal solution. Efficient when buildings are fewer than empty cells.
Multi-pass Grid BFS with Distance + Reach CountersO(kmn)O(mn)Preferred implementation pattern for interviews and production-style grid problems.

Video Solution

LeetCode 317. Shortest Distance from All Buildings Explanation and Solution • happygirlzt • 14,179 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Shortest Distance from All Buildings easy or hard?
Shortest Distance from All Buildings is classified as a Hard problem. The challenge comes from recognizing that running BFS from every empty land is inefficient and that reversing the traversal from buildings allows distance aggregation with O(kmn) complexity.
Shortest Distance from All Buildings Python/Java solution
Most implementations use BFS with a queue and two auxiliary matrices: one for total distance and one for reachable building counts. The algorithm runs BFS from every building, updates distances for reachable empty cells, and finally scans for the minimum valid location. The same logic works across Python, Java, C++, and Go.
How to solve Shortest Distance from All Buildings in O(n)?
The problem cannot be solved in strict O(n) time because grid traversal is required. The best practical complexity is O(kmn), achieved by running BFS from each building and aggregating distances. This avoids repeating BFS from every empty land cell and significantly reduces redundant work.
What is the best approach for Shortest Distance from All Buildings?
The most efficient approach runs Breadth-First Search from each building instead of each empty cell. During BFS, accumulate distances to empty cells and track how many buildings can reach them. After processing all buildings, choose the empty cell reachable from every building with the smallest total distance. This solution runs in O(kmn) time where k is the number of buildings.
Is Shortest Distance from All Buildings asked at Google/Amazon/Meta?
Shortest Distance from All Buildings has appeared in interviews at companies like Google, Amazon, and Meta because it tests grid traversal, BFS fundamentals, and optimization of repeated searches. Interviewers use it to evaluate how candidates improve a brute-force BFS into a more efficient aggregated approach.
What data structure is used in Shortest Distance from All Buildings?
The core data structure is a queue used for Breadth-First Search. Additional 2D arrays track cumulative distance sums and how many buildings can reach each cell. The grid itself acts as a matrix graph where each cell connects to up to four neighbors.
What is the time complexity of Shortest Distance from All Buildings?
The optimal solution runs in O(kmn) time, where m and n are grid dimensions and k is the number of buildings. Each building performs a BFS traversal across the grid once. Space complexity is O(mn) for storing cumulative distance sums and reach counts.

Ready to solve this problem?

Practice Shortest Distance from All Buildings with our built-in code editor and test cases.

Practice on FleetCode
Previous

As Far from Land as Possible

Next

Best Meeting Point