317. Shortest Distance from All Buildings - Leetcode Solution

Code Implementation

from collections import deque

class Solution:
    def shortestDistance(self, grid):
        if not grid or not grid[0]:
            return -1
        m, n = len(grid), len(grid[0])
        total_buildings = sum(val == 1 for row in grid for val in row)
        dist = [[0]*n for _ in range(m)]
        reach = [[0]*n for _ in range(m)]
        dirs = [(-1,0),(1,0),(0,-1),(0,1)]
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    visited = [[False]*n for _ in range(m)]
                    queue = deque()
                    queue.append((i, j, 0))
                    visited[i][j] = True
                    while queue:
                        x, y, d = queue.popleft()
                        for dx, dy in dirs:
                            nx, ny = x+dx, y+dy
                            if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] == 0:
                                visited[nx][ny] = True
                                dist[nx][ny] += d+1
                                reach[nx][ny] += 1
                                queue.append((nx, ny, d+1))
        
        res = float('inf')
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0 and reach[i][j] == total_buildings:
                    res = min(res, dist[i][j])
        return res if res != float('inf') else -1

#include <vector>
#include <queue>
#include <climits>
using namespace std;

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int total_buildings = 0;
        for (auto& row : grid)
            for (int v : row)
                if (v == 1) total_buildings++;
        vector<vector<int>> dist(m, vector<int>(n, 0));
        vector<vector<int>> reach(m, vector<int>(n, 0));
        vector<pair<int,int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    vector<vector<bool>> visited(m, vector<bool>(n, false));
                    queue<tuple<int,int,int>> q;
                    q.emplace(i, j, 0);
                    visited[i][j] = true;
                    while (!q.empty()) {
                        auto [x, y, d] = q.front(); q.pop();
                        for (auto& dir : dirs) {
                            int nx = x + dir.first, ny = y + dir.second;
                            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] == 0) {
                                visited[nx][ny] = true;
                                dist[nx][ny] += d + 1;
                                reach[nx][ny] += 1;
                                q.emplace(nx, ny, d + 1);
                            }
                        }
                    }
                }
            }
        }
        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] == total_buildings)
                    res = min(res, dist[i][j]);
        return res == INT_MAX ? -1 : res;
    }
};

import java.util.*;

public class Solution {
    public int shortestDistance(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int totalBuildings = 0;
        for (int[] row : grid)
            for (int v : row)
                if (v == 1) totalBuildings++;
        int[][] dist = new int[m][n];
        int[][] reach = new int[m][n];
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    boolean[][] visited = new boolean[m][n];
                    Queue<int[]> queue = new LinkedList<>();
                    queue.offer(new int[]{i, j, 0});
                    visited[i][j] = true;
                    while (!queue.isEmpty()) {
                        int[] curr = queue.poll();
                        int x = curr[0], y = curr[1], d = curr[2];
                        for (int[] dir : dirs) {
                            int nx = x + dir[0], ny = y + dir[1];
                            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] == 0) {
                                visited[nx][ny] = true;
                                dist[nx][ny] += d + 1;
                                reach[nx][ny] += 1;
                                queue.offer(new int[]{nx, ny, d + 1});
                            }
                        }
                    }
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 0 && reach[i][j] == totalBuildings)
                    res = Math.min(res, dist[i][j]);
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestDistance = function(grid) {
    const m = grid.length, n = grid[0].length;
    let totalBuildings = 0;
    for (let row of grid)
        for (let v of row)
            if (v === 1) totalBuildings++;
    const dist = Array.from({length: m}, () => Array(n).fill(0));
    const reach = Array.from({length: m}, () => Array(n).fill(0));
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                const visited = Array.from({length: m}, () => Array(n).fill(false));
                const queue = [[i, j, 0]];
                visited[i][j] = true;
                while (queue.length) {
                    const [x, y, d] = queue.shift();
                    for (let [dx, dy] of dirs) {
                        const nx = x + dx, ny = y + dy;
                        if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] === 0) {
                            visited[nx][ny] = true;
                            dist[nx][ny] += d + 1;
                            reach[nx][ny] += 1;
                            queue.push([nx, ny, d + 1]);
                        }
                    }
                }
            }
        }
    }
    let res = Infinity;
    for (let i = 0; i < m; i++)
        for (let j = 0; j < n; j++)
            if (grid[i][j] === 0 && reach[i][j] === totalBuildings)
                res = Math.min(res, dist[i][j]);
    return res === Infinity ? -1 : res;
};

Problem Description

Given a 2D grid of size m x n, each cell in the grid can be:

0: an empty land where you can build a house
1: a building
2: an obstacle (cannot be passed through)

You want to build a house on an empty land such that the total travel distance to all existing buildings is minimized. The travel distance is calculated as the sum of the Manhattan distances from the chosen empty land to each building. You can only move up, down, left, and right.

Return the minimal total distance. If it is not possible to build such a house (i.e., not all buildings are reachable), return -1.

Constraints:

There is at least one building.
You cannot pass through obstacles or buildings.
Each empty land can only be used once.
There is only one valid solution.

Thought Process

The first idea that comes to mind is to try every empty cell and, for each, calculate the total distance to all buildings by performing a BFS (Breadth-First Search) from that cell to every building. However, this brute-force approach is inefficient, especially for larger grids, since it would repeat similar computations multiple times.

Instead, we can optimize by reversing the process: for each building, perform a BFS to every reachable empty land. This way, we accumulate the distances from all buildings to every empty land, and at the end, for each empty cell, we know the sum of distances from all buildings. We can then select the minimum among those that are reachable from every building.

This approach avoids redundant searches and ensures we only consider empty cells that are reachable from every building.

Solution Approach

Step 1: Count the total number of buildings in the grid. This helps us verify at the end whether a cell is reachable from all buildings.
Step 2: For each building (cell with value 1), perform a BFS traversal:
- From the building, traverse to all reachable empty cells (0), keeping track of the distance from the building to each cell.
- For each visited empty cell, accumulate the distance and increment a reach counter indicating how many buildings can reach this cell.
Step 3: After BFS from all buildings, iterate through all empty cells:
- Check if the reach counter for the cell equals the total number of buildings. If so, this cell is reachable from every building.
- Track the minimum accumulated distance among all such cells.
Step 4: Return the minimum total distance found. If no such cell exists (i.e., some buildings are isolated), return -1.

We use BFS for each building because it guarantees the shortest path to each empty land, and we avoid recalculating distances from scratch for every empty cell.

Example Walkthrough

Consider the grid:
[[1, 0, 2, 0, 1], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0]]

Step 1: There are three buildings at positions (0,0), (0,4), and (2,2).
Step 2: For each building, perform BFS to all reachable empty cells, updating the distance and reach counters.
Step 3: After all BFS traversals, for each empty cell, check if it is reachable from all three buildings.
Step 4: Among all such cells, find the one with the lowest total distance. For this grid, the answer is 7.

This process ensures that only cells accessible from all buildings are considered and that the shortest total distance is found efficiently.

Time and Space Complexity

Brute-force Approach:
For each empty cell, perform BFS to each building.
If there are E empty cells and B buildings, and the grid has mn cells, the time complexity is O(E * B * mn), which is very inefficient.
Optimized Approach (Current Solution):
For each building, perform BFS to all empty cells.
If there are B buildings and the grid has mn cells, each BFS takes O(mn) time, so total time is O(B * mn).
Space Complexity:
We maintain two m x n matrices for distances and reach counts, so space is O(mn).

Summary

The key insight is to reverse the brute-force process: instead of checking each empty cell's distance to every building, we BFS from each building to all empty cells. This ensures each empty cell accumulates its total distance from all buildings efficiently. By tracking the reach count, we only consider cells that are reachable from every building. This approach is both elegant and efficient, making it suitable for large grids and complex obstacle layouts.

AlgoMap.io

Want Help Cracking FAANG?