Shortest Distance from All Buildings
Hard · Graphs · Explanation and code example
BFS from Houses to Empty Land (Optimized)
How it works
We can optimize the previous approach by eliminating the separate visited array and the house count tracking. The key insight is to use the grid values themselves as visit markers.
Initially, empty cells have value 0. After the first house's BFS, all reachable empty cells are decremented to -1. The second house's BFS only visits cells with value -1 (reachable by exactly one house), and decrements them to -2. This continues for each house. Cells that become unreachable are naturally pruned.
Steps
- Create a
totalmatrix to accumulate distances. - Initialize
emptyLandValue = 0. - For each house:
- Run
BFS, only visiting cells with value equal toemptyLandValue. - For each visited cell, add the distance to
totaland decrement the cell value. - Track the minimum total distance among cells visited in this
BFS. - Decrement
emptyLandValuefor the next iteration.
- Run
- Return the minimum distance found, or
-1if no valid cell exists.
Complexity
- Time complexity:
O(N^2 × M^2) - Space complexity:
O(N × M)
Where
NandMare the number of rows and columns ingridrespectively.
Things to watch for
Not Checking Reachability to All Houses
An empty cell is only valid if it can reach ALL houses. Simply finding the minimum distance sum is insufficient; you must also verify that the cell can reach every house. Cells that cannot reach all houses should be excluded from consideration, or the solution returns -1 if no valid cell exists.
Incorrect Early Termination
Some implementations try to optimize by stopping BFS early when a house is found. However, BFS from a house must continue to all reachable empty cells to correctly accumulate distances. Early termination leads to incomplete distance sums and incorrect results.
Modifying Grid Without Tracking Reachability
The optimized approach uses decreasing values (0, -1, -2, ...) to track which cells are reachable by all previously processed houses. A common mistake is not understanding that a cell with value k should only be visited by the (|k|+1)-th house's BFS. Cells not matching the expected value are either obstacles, houses, or unreachable from some previous house.
Confusing BFS Direction
There are two valid approaches: BFS from empty cells to houses, or BFS from houses to empty cells. Mixing concepts from both approaches leads to incorrect logic. When doing BFS from houses, each house's BFS contributes distances to empty cells. When doing BFS from empty cells, each empty cell computes its total distance to all houses.
Integer Overflow with Distance Sums
In large grids with many houses, the sum of distances can become very large. Using Integer.MAX_VALUE or similar sentinels for invalid cells, then performing arithmetic operations, can cause overflow. Ensure proper handling of sentinel values in comparisons and avoid adding to them.
Python code example
from typing import List
from collections import deque
class Solution:
def shortestDistance(self, grid: List[List[int]]) -> int:
# Next four directions.
dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
rows = len(grid)
cols = len(grid[0])
# Total Matrix to store total distance sum for each empty cell.
total = [[0] * cols for _ in range(rows)]
empty_land_value = 0
min_dist = float('inf')
for row in range(rows):
for col in range(cols):
# Start a BFS from each house.
if grid[row][col] == 1:
min_dist = float('inf')
# Use a queue to perform a BFS, starting from the cell at (row, col).
q = deque([(row, col)])
steps = 0
while q:
steps += 1
level_size = len(q)
for level in range(level_size):
curr = q.popleft()
for dir in dirs:
next_row = curr[0] + dir[0]
next_col = curr[1] + dir[1]
# For each cell with the value equal to empty land value
# add distance and decrement the cell value by 1.
if (0 <= next_row < rows and
0 <= next_col < cols and
grid[next_row][next_col] == empty_land_value):
grid[next_row][next_col] -= 1
total[next_row][next_col] += steps
q.append((next_row, next_col))
min_dist = min(min_dist, total[next_row][next_col])
# Decrement empty land value to be searched in next iteration.
empty_land_value -= 1
return -1 if min_dist == float('inf') else min_dist
C++ code example
class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
// Next four directions.
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int rows = grid.size();
int cols = grid[0].size();
// Total Matrix to store total distance sum for each empty cell.
vector<vector<int>> total(rows, vector<int> (cols, 0));
int emptyLandValue = 0;
int minDist = INT_MAX;
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
// Start a bfs from each house.
if (grid[row][col] == 1) {
minDist = INT_MAX;
// Use a queue to perform a BFS, starting from the cell located at (row, col).
queue<pair<int, int>> q;
q.push({ row, col });
int steps = 0;
while (!q.empty()) {
steps++;
for (int level = q.size(); level > 0; --level) {
auto curr = q.front();
q.pop();
for (auto& dir : dirs) {
int nextRow = curr.first + dir[0];
int nextCol = curr.second + dir[1];
// For each cell with the value equal to empty land value
// add distance and decrement the cell value by 1.
if (nextRow >= 0 && nextRow < rows &&
nextCol >= 0 && nextCol < cols &&
grid[nextRow][nextCol] == emptyLandValue) {
grid[nextRow][nextCol]--;
total[nextRow][nextCol] += steps;
q.push({ nextRow, nextCol });
minDist = min(minDist, total[nextRow][nextCol]);
}
}
}
}
// Decrement empty land value to be searched in next iteration.
emptyLandValue--;
}
}
}
return minDist == INT_MAX ? -1 : minDist;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.