Quick Overview

Given a grid of empty land, buildings and obstacles, find the empty cell with the smallest total walking distance to every building using four-directional moves, or return -1 when no cell reaches them all. It tests breadth-first search on grids, reachability filtering and edge cases.

Empty Grid Cell With the Smallest Total Walking Distance to All Buildings

Company: Google

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a map as a grid of `m` rows and `n` columns. Each cell holds one of three values: - `0`: empty land, which you may walk through and where a new site may be placed; - `1`: a building, which you cannot walk through; - `2`: an obstacle, which you cannot walk through. From a cell you may move one step up, down, left or right. Choose an empty cell that minimizes the sum, over all buildings, of the shortest walking distance from that cell to the building, and return that minimum sum. If no empty cell can reach every building, return `-1`. ### Function Signature ```python def min_total_distance_to_buildings(grid: list[list[int]]) -> int: ``` ### Rules - The distance from an empty cell to a building is the smallest number of steps in a path that starts at the empty cell, moves only through empty cells, and whose final step enters the building's cell. If no such path exists, that building is unreachable from the cell. - Buildings and obstacles are never walked through, and they can never be the chosen cell. A building can appear in a path only as its final cell. - An empty cell is a valid choice only if every building in the grid is reachable from it. - Return the smallest total distance over all valid cells. The answer is a single integer, so it does not matter which cell achieves it when several tie. - Return `-1` when there is no valid cell, including when the grid contains no building at all or no empty cell. ### Constraints - `1 <= m, n <= 50` - Every row has exactly `n` entries, and each entry is `0`, `1` or `2`. - Any total distance is below `2500 * 2500 = 6,250,000`, well within a 32-bit signed integer. ### Examples **Example 1** ```text Input: grid = [[1, 0, 1], [0, 0, 0], [2, 1, 0]] Output: 4 ``` ```text 1 0 1 0 0 0 2 1 0 ``` The buildings are at (0, 0), (0, 2) and (2, 1), and (2, 0) is an obstacle. Cell (0, 1) is 1 step from (0, 0), 1 step from (0, 2), and 2 steps from (2, 1) through (1, 1), for a total of 4. The other empty cells total 5 for (1, 1), 6 for (1, 0), 6 for (1, 2) and 7 for (2, 2). **Example 2** ```text Input: grid = [[1, 1, 0]] Output: -1 ``` The only empty cell is (0, 2). Building (0, 1) is one step away, but reaching building (0, 0) would require walking through (0, 1), which is a building. No empty cell reaches every building. **Example 3** ```text Input: grid = [[0, 2], [2, 0]] Output: -1 ``` The grid contains no building, so by the rules the answer is `-1`.

Overview: Given a grid of empty land, buildings and obstacles, find the empty cell with the smallest total walking distance to every building using four-directional moves, or return -1 when no cell reaches them all. It tests breadth-first search on grids, reachability filtering and edge cases.

You are given a map as a grid `grid` of `m` rows and `n` columns. Each cell holds one of three values: - `0`: empty land, which you may walk through and where a new site may be placed; - `1`: a building, which you cannot walk through; - `2`: an obstacle, which you cannot walk through. From a cell you may move one step up, down, left or right. Choose an empty cell that minimizes the sum, over all buildings, of the shortest walking distance from that cell to the building, and return that minimum sum. If no empty cell can reach every building, return `-1`. Implement `min_total_distance_to_buildings(grid)`. Cells are written as (row, column), counted from 0. **Rules** - The distance from an empty cell to a building is the smallest number of steps in a path that starts at the empty cell, moves only through empty cells, and whose final step enters the building's cell. If no such path exists, that building is unreachable from the cell. - Buildings and obstacles are never walked through, and they can never be the chosen cell. A building can appear in a path only as its final cell. - An empty cell is a valid choice only if every building in the grid is reachable from it. - Return the smallest total distance over all valid cells. The answer is a single integer, so it does not matter which cell achieves it when several tie. - Return `-1` when there is no valid cell, including when the grid contains no building at all or no empty cell. **Example 1** ``` Input: grid = [[1, 0, 1], [0, 0, 0], [2, 1, 0]] Output: 4 ``` The buildings are at (0, 0), (0, 2) and (2, 1), and (2, 0) is an obstacle. Cell (0, 1) is 1 step from (0, 0), 1 step from (0, 2), and 2 steps from (2, 1) through (1, 1), for a total of 4. The other empty cells total 5 for (1, 1), 6 for (1, 0), 6 for (1, 2) and 7 for (2, 2). **Example 2** ``` Input: grid = [[1, 1, 0]] Output: -1 ``` The only empty cell is (0, 2). Building (0, 1) is one step away, but reaching building (0, 0) would require walking through (0, 1), which is a building. No empty cell reaches every building. **Constraints** - `1 <= m, n <= 50` - Every row has exactly `n` entries, and each entry is `0`, `1` or `2`. - Any total distance is below `2500 * 2500 = 6,250,000`, well within a 32-bit signed integer: the answer never exceeds 2^31 - 1, so Java and C++ return `int`.

Constraints

  • 1 <= m, n <= 50
  • Every row has exactly n entries, and each entry is 0, 1 or 2.
  • Any total distance is below 2500 * 2500 = 6,250,000, well within a 32-bit signed integer.

Examples

Input: ([[1, 0, 1], [0, 0, 0], [2, 1, 0]],)

Expected Output: 4

Explanation: Source Example 1: cell (0, 1) totals 1 + 1 + 2 = 4; the other empty cells total 5, 6, 6 and 7.

Input: ([[1, 1, 0]],)

Expected Output: -1

Explanation: Source Example 2: the only empty cell would have to walk through building (0, 1) to reach building (0, 0), so no cell is valid.

Hints

  1. A cell is a valid site only if every building can be reached from it; a cell that is very close to some buildings but cut off from even one of them cannot be chosen.
  2. Movement stops at buildings and obstacles: a path may end on a building but never pass through one, so a walking distance can be longer than the straight grid distance.
  3. When there is no building, no empty cell, or no empty cell that reaches every building, the answer is -1.

Best Empty Lot by Total Walking Distance to All Buildings

hardGoogleMachine Learning Engineer

You are given a map as a grid grid of m rows and n columns. Each cell holds one of three values:

  • 0: empty land, which you may walk through and where a new site may be placed;
  • 1: a building, which you cannot walk through;
  • 2: an obstacle, which you cannot walk through.

From a cell you may move one step up, down, left or right. Choose an empty cell that minimizes the sum, over all buildings, of the shortest walking distance from that cell to the building, and return that minimum sum. If no empty cell can reach every building, return -1.

Implement min_total_distance_to_buildings(grid). Cells are written as (row, column), counted from 0.

Rules

  • The distance from an empty cell to a building is the smallest number of steps in a path that starts at the empty cell, moves only through empty cells, and whose final step enters the building's cell. If no such path exists, that building is unreachable from the cell.
  • Buildings and obstacles are never walked through, and they can never be the chosen cell. A building can appear in a path only as its final cell.
  • An empty cell is a valid choice only if every building in the grid is reachable from it.
  • Return the smallest total distance over all valid cells. The answer is a single integer, so it does not matter which cell achieves it when several tie.
  • Return -1 when there is no valid cell, including when the grid contains no building at all or no empty cell.

Example 1

Input:  grid = [[1, 0, 1], [0, 0, 0], [2, 1, 0]]
Output: 4

The buildings are at (0, 0), (0, 2) and (2, 1), and (2, 0) is an obstacle. Cell (0, 1) is 1 step from (0, 0), 1 step from (0, 2), and 2 steps from (2, 1) through (1, 1), for a total of 4. The other empty cells total 5 for (1, 1), 6 for (1, 0), 6 for (1, 2) and 7 for (2, 2).

Example 2

Input:  grid = [[1, 1, 0]]
Output: -1

The only empty cell is (0, 2). Building (0, 1) is one step away, but reaching building (0, 0) would require walking through (0, 1), which is a building. No empty cell reaches every building.

Constraints

  • 1 <= m, n <= 50
  • Every row has exactly n entries, and each entry is 0, 1 or 2.
  • Any total distance is below 2500 * 2500 = 6,250,000, well within a 32-bit signed integer: the answer never exceeds 2^31 - 1, so Java and C++ return int.

Examples

Example 1
Input
([[1, 0, 1], [0, 0, 0], [2, 1, 0]],)
Output
4
Notes
Source Example 1: cell (0, 1) totals 1 + 1 + 2 = 4; the other empty cells total 5, 6, 6 and 7.
Example 2
Input
([[1, 1, 0]],)
Output
-1
Notes
Source Example 2: the only empty cell would have to walk through building (0, 1) to reach building (0, 0), so no cell is valid.

Constraints

  • •1 <= m, n <= 50
  • •Every row has exactly n entries, and each entry is 0, 1 or 2.
  • •Any total distance is below 2500 * 2500 = 6,250,000, well within a 32-bit signed integer.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def min_total_distance_to_buildings(grid: list[list[int]]) -> int:
Sample call
min_total_distance_to_buildings([[1, 0, 1], [0, 0, 0], [2, 1, 0]])
Language
Case 1
Input
([[1, 0, 1], [0, 0, 0], [2, 1, 0]],)
Expected
4
Case 2
Input
([[1, 1, 0]],)
Expected
-1

Browse More Questions

Show the approach

Approach

Run one breadth-first search from each building, stepping only into empty cells. Walking from an empty cell to a building and walking from the building back to that cell use the same sequence of empty cells, so the depth at which a building's search first reaches a cell is exactly that cell's walking distance to the building, and buildings are never expanded, so no path passes through one. For every empty cell keep the running sum of these distances and the number of buildings whose search reached it. Invariant: before the k-th building's search, a cell can still be valid only if all k earlier searches reached it, so the k-th search steps only into cells reached exactly k times and marks each one as reached k + 1 times (which also serves as its visited flag). Whether a building is reachable is the same for every cell of one connected group of empty cells, so this pruning removes whole groups and never changes a shortest path inside a group that stays eligible. If a search reaches no eligible cell, no cell can be valid and the function returns -1 at once. After all searches, the answer is the smallest sum among empty cells reached by every building. Edge cases: a grid with no building returns -1 as the rules require; a grid with no empty cell returns -1 because the first search reaches nothing; a cell cut off from even one building is excluded however close it is to the others; ties do not matter because only the minimum value is returned; every total is below 6,250,000, so 32-bit integers suffice.

Time complexity:
O(B * m * n), where B is the number of buildings
Space complexity:
O(m * n)