Shortest Distance from all Buildings
XXX. Shortest Distance from All Buildings
Graph
BFS
Matrix
Problem Statement:
Given a 2D grid where 1 represents buildings and 0 represents empty land, find the empty land point that has the shortest total distance to all buildings. Return -1 if it's impossible.
- Distance is calculated as Manhattan distance
- Can only move up, down, left, or right
- Must be able to reach all buildings from the chosen point
- Grid cells with value 2 represent obstacles
Algorithm:
-
**Initial Setup**:
- Track total distance for each empty cell
- Count number of reachable buildings for each cell
- Collect all building positions
-
**BFS Process**:
- Run BFS from each building
- Update distances and reachable building counts
- Skip visited cells and obstacles
-
**Result Finding**:
- Check cells that can reach all buildings
- Find minimum total distance among valid cells
Complexity:
Time Complexity: O(k * m * n), where k is number of buildings, m and n are grid dimensions
Space Complexity: O(m * n) for distance and building count arrays
Implementation:
Java Solution:
class Solution {
public int shortestDistance(int[][] grid) {
int m = grid.length, n = grid[0].length;
int min = Integer.MAX_VALUE;
int[][] numBuildings = new int[m][n]; // Track reachable buildings
int[][] dist = new int[m][n]; // Track total distances
List buildings = new ArrayList<>();
// Collect building positions
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1)
buildings.add(new Tuple(i, j, 0));
// Run BFS from each building
for (Tuple building : buildings)
bfs(building, grid, new boolean[m][n], dist, numBuildings);
// Find minimum distance point that reaches all buildings
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (numBuildings[i][j] == buildings.size())
min = Math.min(min, dist[i][j]);
return min == Integer.MAX_VALUE ? -1 : min;
}
private void bfs(Tuple root, int[][] grid, boolean[][] visited, int[][] dist, int[][] numBuildings) {
int m = grid.length, n = grid[0].length;
Queue q = new LinkedList<>();
q.add(root);
int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1}; // Direction arrays
while (!q.isEmpty()) {
Tuple curr = q.poll();
dist[curr.x][curr.y] += curr.dist;
for (int i = 0; i < 4; i++) {
int newX = curr.x + dx[i], newY = curr.y + dy[i];
if (newX >= 0 && newY >= 0 && newX < m && newY < n && !visited[newX][newY] && grid[newX][newY] == 0) {
q.add(new Tuple(newX, newY, curr.dist + 1));
visited[newX][newY] = true;
numBuildings[newX][newY]++;
}
}
}
}
}
class Tuple {
int x, y, dist;
public Tuple(int x, int y, int dist) {
this.x = x;
this.y = y;
this.dist = dist;
}
}
Python Solution:
class Solution:
def shortestDistance(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
buildings = [(i, j, 0) for i in range(m) for j in range(n) if grid[i][j] == 1]
dist = [[0] * n for _ in range(m)] # Track total distances
num_buildings = [[0] * n for _ in range(m)] # Track reachable buildings
def bfs(root):
x, y, d = root
visited = [[False] * n for _ in range(m)]
q = deque([(x, y, d)])
while q:
cx, cy, cd = q.popleft()
dist[cx][cy] += cd
for dx, dy in [(1,0), (0,1), (-1,0), (0,-1)]:
nx, ny = cx + dx, cy + dy
if (0 <= nx < m and 0 <= ny < n and
not visited[nx][ny] and grid[nx][ny] == 0):
q.append((nx, ny, cd + 1))
visited[nx][ny] = True
num_buildings[nx][ny] += 1
# Run BFS from each building
for building in buildings:
bfs(building)
# Find minimum distance point
min_dist = float('inf')
for i in range(m):
for j in range(n):
if num_buildings[i][j] == len(buildings):
min_dist = min(min_dist, dist[i][j])
return min_dist if min_dist != float('inf') else -1
C++ Solution:
class Solution {
struct Tuple {
int x, y, dist;
Tuple(int x, int y, int d) : x(x), y(y), dist(d) {}
};
void bfs(Tuple& root, vector>& grid, vector>& visited,
vector>& dist, vector>& numBuildings) {
int m = grid.size(), n = grid[0].size();
queue q;
q.push(root);
vector dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
while (!q.empty()) {
auto curr = q.front(); q.pop();
dist[curr.x][curr.y] += curr.dist;
for (int i = 0; i < 4; i++) {
int newX = curr.x + dx[i], newY = curr.y + dy[i];
if (newX >= 0 && newY >= 0 && newX < m && newY < n &&
!visited[newX][newY] && grid[newX][newY] == 0) {
q.push(Tuple(newX, newY, curr.dist + 1));
visited[newX][newY] = true;
numBuildings[newX][newY]++;
}
}
}
}
public:
int shortestDistance(vector>& grid) {
int m = grid.size(), n = grid[0].size();
vector> dist(m, vector(n));
vector> numBuildings(m, vector(n));
vector buildings;
// Collect buildings
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1)
buildings.push_back(Tuple(i, j, 0));
// Run BFS from each building
for (auto& building : buildings) {
vector> visited(m, vector(n));
bfs(building, grid, visited, dist, numBuildings);
}
// Find minimum distance point
int minDist = INT_MAX;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (numBuildings[i][j] == buildings.size())
minDist = min(minDist, dist[i][j]);
return minDist == INT_MAX ? -1 : minDist;
}
};
Explanation:
-
**Distance Tracking**:
- Accumulate distances from each building
- Track number of reachable buildings for each cell
- Only consider cells that can reach all buildings
-
**BFS Implementation**:
- Use queue for level-order traversal
- Track visited cells for each BFS run
- Update distances and building counts during traversal
-
**Optimization Notes**:
- Separate visited array for each BFS
- Early termination if no valid path exists
- Direction arrays for clean movement code
