Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Solution: Shortest Distance from All Buildings

Explore how to compute the shortest total distance from a potential house location to all buildings in a grid with obstacles. Learn to apply a BFS approach from each building to empty land cells, accumulating reachability and minimum distances. Understand the algorithm's logic, BFS implementation details, and optimize with auxiliary grids to ensure every building is reachable from the chosen cell.

We'll cover the following...

Statement

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

  • 00 represents empty land that can be freely traversed,

  • 11 represents a building that cannot be passed through,

  • 22 represents an obstacle that cannot be passed through.

You want to place a house on an empty land cell (00) 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-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

  • ...