Hard
Subtopics
array·breadth-first-search·matrix
Companies
amazon·bytedance·facebook·goldman-sachs·google·mathworks·microsoft·snapchat·splunk·uber·zenefitsLast updated: Aug 1, 2025
You are given an m x n grid grid of values 0, 1, or 2, where:
each 0 marks an empty land that you can pass by freely,
each 1 marks a building that you cannot pass through, and
each 2 marks an obstacle that you cannot pass through.
You want to build a house on an empty land that reaches all buildings in the shortest total travel distance. You can only move up, down, left, and right.
Return the shortest travel distance for such a house. If it is not possible to build such a house according to the above rules, return -1.
The total travel distance is the sum of the distances between the houses of the friends and the meeting point.
The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.
Input: grid =[[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]Output: 7Explanation: Given three buildings at(0,0),(0,4),(2,2), and an obstacle at(0,2).The point(1,2)is an ideal empty land to build a house, as the total travel distance of 3+3+1=7is minimal.So return7.
For each building, we perform BFS to calculate the shortest distance from that building to every empty land. We accumulate the total distance and track how many buildings can reach each cell. The answer is the minimum total distance among all empty lands that can be reached by all buildings.
classSolution {
public:int shortestDistance(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> distance(m, vector<int>(n, 0));
vector<vector<int>> reach(m, vector<int>(n, 0));
int numBuildings =0;
vector<pair<int, int>> dirs = {{0,1},{1,0},{0,-1},{-1,0}};
for (int i =0; i < m; ++i) {
for (int j =0; j < n; ++j) {
if (grid[i][j] ==1) {
numBuildings++;
vector<vector<bool>> visited(m, vector<bool>(n, false));
queue<pair<int, int>> q;
q.push({i, j});
int dist =0;
visited[i][j] = true;
while (!q.empty()) {
int sz = q.size();
dist++;
for (int k =0; k < sz; ++k) {
auto [x, y] = q.front(); q.pop();
for (auto& d : dirs) {
int nx = x + d.first, ny = y + d.second;
if (nx >=0&& nx < m && ny >=0&& ny < n &&!visited[nx][ny] && grid[nx][ny] ==0) {
visited[nx][ny] = true;
distance[nx][ny] += dist;
reach[nx][ny]++;
q.push({nx, ny});
}
}
}
}
}
}
}
int res = INT_MAX;
for (int i =0; i < m; ++i) {
for (int j =0; j < n; ++j) {
if (grid[i][j] ==0&& reach[i][j] == numBuildings) {
res = min(res, distance[i][j]);
}
}
}
return res == INT_MAX ?-1: res;
}
};
classSolution {
funshortestDistance(grid: Array<IntArray>): Int {
val m = grid.size
val n = grid[0].size
val distance = Array(m) { IntArray(n) }
val reach = Array(m) { IntArray(n) }
val dirs = arrayOf(intArrayOf(0,1), intArrayOf(1,0), intArrayOf(0,-1), intArrayOf(-1,0))
var numBuildings = 0for (i in0 until m) {
for (j in0 until n) {
if (grid[i][j] ==1) {
numBuildings++val visited = Array(m) { BooleanArray(n) }
val q: Queue<Pair<Int, Int>> = LinkedList()
q.offer(Pair(i, j))
var dist = 0 visited[i][j] = truewhile (q.isNotEmpty()) {
dist++ repeat(q.size) {
val(x, y) = q.poll()
for (d in dirs) {
val nx = x + d[0]
val ny = y + d[1]
if (nx in0 until m && ny in0 until n && !visited[nx][ny] && grid[nx][ny] ==0) {
visited[nx][ny] = true distance[nx][ny] += dist
reach[nx][ny]++ q.offer(Pair(nx, ny))
}
}
}
}
}
}
}
var res = Int.MAX_VALUE
for (i in0 until m) {
for (j in0 until n) {
if (grid[i][j] ==0&& reach[i][j] == numBuildings) {
res = minOf(res, distance[i][j])
}
}
}
returnif (res ==Int.MAX_VALUE) -1else res
}
}
from collections import deque
classSolution:
defshortestDistance(self, grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
distance = [[0]*n for _ in range(m)]
reach = [[0]*n for _ in range(m)]
dirs = [(0,1),(1,0),(0,-1),(-1,0)]
numBuildings =0for i in range(m):
for j in range(n):
if grid[i][j] ==1:
numBuildings +=1 visited = [[False]*n for _ in range(m)]
q = deque([(i, j)])
dist =0 visited[i][j] =Truewhile q:
dist +=1for _ in range(len(q)):
x, y = q.popleft()
for dx, dy in dirs:
nx, ny = x+dx, y+dy
if0<= nx < m and0<= ny < n andnot visited[nx][ny] and grid[nx][ny] ==0:
visited[nx][ny] =True distance[nx][ny] += dist
reach[nx][ny] +=1 q.append((nx, ny))
res = float('inf')
for i in range(m):
for j in range(n):
if grid[i][j] ==0and reach[i][j] == numBuildings:
res = min(res, distance[i][j])
return-1if res == float('inf') else res
use std::collections::VecDeque;
impl Solution {
pubfnshortest_distance(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
letmut distance =vec![vec![0; n]; m];
letmut reach =vec![vec![0; n]; m];
let dirs = [(0,1),(1,0),(0,-1),(-1,0)];
letmut num_buildings =0;
for i in0..m {
for j in0..n {
if grid[i][j] ==1 {
num_buildings +=1;
letmut visited =vec![vec![false; n]; m];
letmut q = VecDeque::new();
q.push_back((i, j));
letmut dist =0;
visited[i][j] =true;
while!q.is_empty() {
dist +=1;
for _ in0..q.len() {
let (x, y) = q.pop_front().unwrap();
for (dx, dy) in dirs.iter() {
let nx = x asi32+ dx;
let ny = y asi32+ dy;
if nx >=0&& nx < m asi32&& ny >=0&& ny < n asi32 {
let nx = nx asusize;
let ny = ny asusize;
if!visited[nx][ny] && grid[nx][ny] ==0 {
visited[nx][ny] =true;
distance[nx][ny] += dist;
reach[nx][ny] +=1;
q.push_back((nx, ny));
}
}
}
}
}
}
}
}
letmut res = std::i32::MAX;
for i in0..m {
for j in0..n {
if grid[i][j] ==0&& reach[i][j] == num_buildings {
res = res.min(distance[i][j]);
}
}
}
if res == std::i32::MAX { -1 } else { res }
}
}