Shortest Distance from All Buildings
Hard · Matrix · Array · Breadth-First Search · Matrix
Problem
You are given an m x n grid where 0 is empty land you can walk through, 1 is a building, and 2 is an obstacle. You want to build a house on one empty cell so that the total travel distance to every building is as small as possible.
Travel moves up, down, left or right, one cell per step, and only through empty land: you cannot pass through buildings or obstacles, and a building is only ever a destination. The total travel distance is the sum of the shortest walking distances from the house to each building.
Return the minimum total travel distance, or -1 if no empty cell can reach every building.
Examples
Input: grid = [[1,0,0,1],[0,2,0,0],[0,0,1,0]] Output: 5
A house at (0,2) is 2, 1 and 2 steps from the three buildings, a total of 5, and no empty cell does better.
Input: grid = [[1,0]] Output: 1
The only empty cell is one step from the only building.
Input: grid = [[1,2,0]] Output: -1
The obstacle cuts the building off from the only empty cell.
Constraints
- m == len(grid), n == len(grid[i])
- 1 <= m, n <= 50
- grid[i][j] is 0, 1 or 2
- There is at least one building
Approaches
- Baseline: BFS from every empty cell — time O(E · m · n), space O(m · n)
Follow-up
With no obstacles at all, walking distance becomes Manhattan distance and rows and columns separate: the best point is at the median row and the median column (see the use case “Best meeting point on an open grid”). And if you minimized the longest walk instead of the total, the same searches work with max in place of +.
Related problems
Start free on Cariara · Coding problems · System design studio
