Shortest Distance from All Buildings - Solution & Explanation

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.