Minimize Total Grid Distance to Every Building
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a rectangular grid containing buildings, empty land, and obstacles, choose an empty cell that minimizes the sum of its shortest-path distances to every building. Return that minimum sum, or `-1` if no empty cell can reach every building.
### Input
- `grid`: a two-dimensional integer array. A `0` is empty land, a `1` is a building, and a `2` is an obstacle.
### Output
Return the minimum total distance as an integer. Return only the distance, so tied locations do not require a tie-break.
### Constraints and Edge Cases
- For this practice version, the grid has between `1` and `50` rows and between `1` and `50` columns.
- At least one building is present.
- One move enters an orthogonally adjacent cell and has cost one. Diagonal movement is not allowed.
- Intermediate cells on a path must be empty land. A building may be the destination, but a path cannot pass through it to reach another building.
- Obstacles cannot be entered.
- If no empty land exists, or no empty cell reaches every building, return `-1`.
### Example 1
```text
grid = [[1,0,2], [0,0,0], [2,0,1]]
output = 4
```
The center cell has distance two to each building, for a total of four. No candidate has a smaller sum.
### Example 2
```text
grid = [[1,0,1,0,1]]
output = -1
```
The middle building blocks travel between the two empty cells. Neither candidate can reach all three buildings without passing through a building.
Overview: Find an empty grid cell minimizing total shortest-path distance to all buildings while respecting obstacles and building traversal restrictions.
Read the full Waymo Software Engineer interview experience this question came from
Given a rectangular grid containing buildings, empty land, and obstacles, choose an empty cell that minimizes the sum of its shortest-path distances to every building. Return that minimum sum, or `-1` if no empty cell can reach every building.
### Input
- `grid`: a two-dimensional integer array. A `0` is empty land, a `1` is a building, and a `2` is an obstacle.
### Output
Return the minimum total distance as an integer. Return only the distance, so tied locations do not require a tie-break.
### Constraints and Edge Cases
- For this practice version, the grid has between `1` and `50` rows and between `1` and `50` columns.
- At least one building is present.
- One move enters an orthogonally adjacent cell and has cost one. Diagonal movement is not allowed.
- Intermediate cells on a path must be empty land. A building may be the destination, but a path cannot pass through it to reach another building.
- Obstacles cannot be entered.
- If no empty land exists, or no empty cell reaches every building, return `-1`.
### Example 1
```text
grid = [[1,0,2], [0,0,0], [2,0,1]]
output = 4
```
The center cell has distance two to each building, for a total of four. No candidate has a smaller sum.
### Example 2
```text
grid = [[1,0,1,0,1]]
output = -1
```
The middle building blocks travel between the two empty cells. Neither candidate can reach all three buildings without passing through a building.
Constraints
- grid has 1 through 50 rows and 1 through 50 columns.
- Cells are 0 for empty land, 1 for a building, and 2 for an obstacle; at least one building is present.
- Moves are orthogonal with unit cost. Only empty cells may be intermediate path cells; a building may be entered only as the destination.
- Choose an empty cell reaching every building and return its minimum total distance; otherwise return -1.
Examples
Input: ([[1, 0, 2], [0, 0, 0], [2, 0, 1]],)
Expected Output: 4
Explanation: Published sample 1: the center has distance two to each building.
Input: ([[1, 0, 1, 0, 1]],)
Expected Output: -1
Explanation: Published sample 2: the middle building cannot be used as an intermediate cell.