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.

Description Solution Video 12:25

317. Shortest Distance from All Buildings

Hard44.9% acceptance15 companiesPremium elsewhere, free here

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: