Solution: Shortest Distance from All Buildings

Understand how to apply breadth-first search to calculate the shortest total distance from an empty land cell to all buildings in a grid. Learn to reverse BFS from buildings, accumulate distances, and find the minimum valid placement efficiently, mastering spatial traversal and optimization in grid problems.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

Given an m x n integer grid grid, where each cell contains one of three values:

$0$ represents empty land that can be freely traversed,
$1$ represents a building that cannot be passed through,
$2$ represents an obstacle that cannot be passed through.

You want to place a house on an empty land cell ( $0$ ) such that the sum of shortest distances from the house to all buildings is minimized. Movement is restricted to four directions: up, down, left, and right.

Return the minimum total travel distance for such a placement. If no valid empty land cell can reach all buildings, return $-1$ .

Note: The total travel distance is the sum of the shortest path distances from the chosen empty land cell to every building in the grid.

Constraints:

m == grid.length
n == grid[i].length
...