Solution: Shortest Distance from All Buildings

Explore how to efficiently solve the shortest distance problem from all buildings in a grid by applying breadth-first search from buildings. Understand the use of auxiliary grids to accumulate distances and reach counts, and learn to identify the optimal empty land cell placement. This lesson covers BFS traversal techniques and complexity analysis in grid-based 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
...