Find the Best Meeting Point on a Grid
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Find the Best Meeting Point on a Grid
You are given a rectangular grid containing buildings, empty land, and obstacles:
- `1` is a building.
- `0` is empty land that can be traversed and selected.
- `2` is an obstacle that cannot be traversed.
Movement is allowed one cell at a time in the four cardinal directions. Choose an empty cell that is reachable from every building and minimizes the sum of shortest-path distances from all buildings. Return that minimum sum, or `-1` if no such empty cell exists.
## Function Contract
```python
def shortest_total_distance(grid: list[list[int]]) -> int:
...
```
## Constraints
- `1 <= rows, columns <= 50`
- Every cell is `0`, `1`, or `2`.
- The grid contains at least one building.
- Buildings and obstacles are not traversable.
- Do not mutate the caller's grid.
## Examples
```text
grid = [
[1, 0, 2, 0, 1],
[0, 0, 0, 0, 0],
[0, 0, 1, 0, 0],
]
result = 7
```
Quick Answer: Find an empty grid cell reachable from every building that minimizes the total shortest-path distance. Buildings and obstacles cannot be crossed, the grid can be 50 by 50, and the result must distinguish the best meeting point from cases with no common reachable land.
Implement shortest_total_distance(grid). Cells are buildings (1), traversable/selectable empty land (0), or impassable obstacles (2). Choose an empty cell reachable from every building that minimizes the sum of four-directional shortest-path distances. Return that sum, or -1 when no qualifying empty cell exists. Buildings and obstacles are not traversable, and the input must not be mutated.
Constraints
- 1 <= rows, columns <= 50
- Every cell is 0, 1, or 2, and at least one building exists.
- Only empty cells are traversable and selectable.
- The caller's grid must not be mutated.
Examples
Input: ([[1, 0, 2, 0, 1], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0]],)
Expected Output: 7
Explanation: The sample's central meeting area gives total distance seven.
Input: ([[1, 0]],)
Expected Output: 1
Explanation: The only empty cell is adjacent to the building.
Hints
- Run BFS from each building through empty cells.
- For every empty cell, accumulate both total distance and the number of buildings that reached it.