[Hard] 317. Shortest Distance from All Buildings

This is a graph traversal problem that requires finding the optimal location to build a new building such that the total distance to all existing buildings is minimized. The key insight is using BFS from each building to calculate distances and finding the spot with minimum total distance.

Problem Description

Given a 2D grid where:

  • 0 represents empty land
  • 1 represents a building
  • 2 represents an obstacle

Find the shortest distance from all buildings to a single empty land cell. Return -1 if it’s impossible.

Examples

Example 1:

Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7
Explanation: The optimal location is (1,2) with total distance 7.

Example 2:

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

Example 3:

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

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] is either 0, 1, or 2
  • There will be at least one building in the grid

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

  1. Grid cell types: What do the values represent? (Assumption: 0 = empty land, 1 = building, 2 = obstacle - cannot pass through)

  2. Distance calculation: How is distance calculated? (Assumption: Manhattan distance - sum of horizontal and vertical steps, can only move in 4 directions)

  3. Reachability: Must the empty land be reachable from all buildings? (Assumption: Yes - if cannot reach all buildings, return -1)

  4. Obstacle handling: Can we pass through obstacles? (Assumption: No - obstacles block movement, cannot build on obstacles)

  5. Return value: What should we return? (Assumption: Shortest total distance from chosen empty land to all buildings, or -1 if impossible)

Interview Deduction Process (30 minutes)

Step 1: Brute-Force Approach (8 minutes)

Initial Thought: “I need to find shortest distance. Let me try each empty land position.”

Naive Solution: For each empty land cell, perform BFS to all buildings, sum distances, find minimum.

Complexity: O(m × n × B) time where B is building count, O(m × n) space

Issues:

  • O(m × n × B) time - inefficient
  • Repeats BFS for each empty land
  • Doesn’t leverage reverse BFS
  • Can be optimized significantly

Step 2: Semi-Optimized Approach (10 minutes)

Insight: “I can BFS from each building to all empty lands, accumulate distances.”

Improved Solution: For each building, perform BFS to all reachable empty lands, accumulate distances. Find empty land with minimum total distance.

Complexity: O(B × m × n) time, O(m × n) space

Improvements:

  • BFS from buildings is more efficient
  • Accumulates distances correctly
  • Still O(B × m × n) but better structure
  • Can optimize further

Step 3: Optimized Solution (12 minutes)

Final Optimization: “BFS from buildings with distance accumulation is optimal. Can optimize with grid modification.”

Best Solution: BFS from each building, accumulate distances in distance matrix. Use grid modification to track reachability. Find empty land reachable from all buildings with minimum distance.

Complexity: O(B × m × n) time, O(m × n) space

Key Realizations:

  1. BFS from buildings is key insight
  2. Distance accumulation enables efficient computation
  3. Grid modification tracks reachability
  4. O(B × m × n) time is optimal for this approach

Approach

There are three main approaches to solve this problem:

  1. BFS from Each Empty Land: For each empty land, BFS to all buildings
  2. BFS from Each Building: For each building, BFS to all empty lands and accumulate distances
  3. Optimized BFS with Grid Modification: Use grid values to track reachability

Solution 1: BFS from Each Empty Land

Time Complexity: O(m²n²) - For each empty land, BFS to all buildings
Space Complexity: O(mn) - For visited array and queue

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        const int rows = grid.size();
        const int cols = grid[0].size();

        int totalHouses = 0;
        for (const auto& row : grid) {
            for (const auto& cell : row) {
                if (cell == 1) totalHouses++;
            }
        }

        int minDistance = INT_MAX;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == 0) {
                    minDistance = std::min(minDistance, bfs(grid, r, c, totalHouses));
                }
            }
        }

        return (minDistance == INT_MAX) ? -1 : minDistance;
    }

private:
    int bfs(vector<vector<int>>& grid, int startRow, int startCol, int totalHouses) {
        constexpr array<pair<int, int>, 4> directions\{\{
            \{1, 0\}, \{-1, 0\}, \{0, 1\}, \{0, -1\}
        \}\};

        const int rows = grid.size();
        const int cols = grid[0].size();

        int distanceSum = 0;
        int housesReached = 0;
        int steps = 0;

        queue<pair<int, int>> q;
        q.emplace(startRow, startCol);

        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        visited[startRow][startCol] = true;

        while (!q.empty() && housesReached != totalHouses) {
            const int levelSize = q.size();

            for (int i = 0; i < levelSize; ++i) {
                auto [r, c] = q.front();
                q.pop();

                if (grid[r][c] == 1) {
                    distanceSum += steps;
                    ++housesReached;
                    continue;
                }

                for (const auto& [dr, dc] : directions) {
                    int nr = r + dr;
                    int nc = c + dc;

                    if (nr >= 0 && nc >= 0 && nr < rows && nc < cols &&
                        !visited[nr][nc] && grid[nr][nc] != 2) {
                        visited[nr][nc] = true;
                        q.emplace(nr, nc);
                    }
                }
            }
            steps++;
        }

        if (housesReached != totalHouses) {
            for (int r = 0; r < rows; ++r) {
                for (int c = 0; c < cols; ++c) {
                    if (grid[r][c] == 0 && visited[r][c]) {
                        grid[r][c] = 2;  // Mark as unreachable
                    }
                }
            }
            return INT_MAX;
        }

        return distanceSum;
    }
};

Solution 2: BFS from Each Building

Time Complexity: O(m²n²) - For each building, BFS to all empty lands
Space Complexity: O(mn) - For distance tracking and visited array

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        const int cols = grid[0].size(), rows = grid.size();
        int minDisatnce = INT_MAX, totalHouses = 0;
        vector<vector<array<int, 2>>> distances(rows, vector<array<int, 2>> (cols, {0, 0}));
        for(int row = 0; row < rows; row++) {
            for(int col = 0; col < cols; col++) {
                if(grid[row][col] == 1) {
                    totalHouses++;
                    bfs(grid, distances, row, col);
                }
            }
        }
        for (int row = 0; row < rows; row++) {
            for(int col = 0; col < cols; col++) {
                if(distances[row][col][1] == totalHouses) {
                    minDisatnce = min(minDisatnce, distances[row][col][0]);
                }
            }
        }
        return minDisatnce == INT_MAX ? -1: minDisatnce;
    }

private:
    void bfs(vector<vector<int>>& grid, vector<vector<array<int, 2>>>& distance, int row, int col) {
        constexpr array<pair<int, int>, 4> dirs = \{\{\{1, 0\}, \{-1, 0\}, \{0, 1\}, \{0, -1\}\}\};
        const int rows = grid.size(), cols = grid[0].size();
        queue<pair<int, int>> q;
        q.emplace(row, col);
        vector<vector<bool>> vis (rows, vector<bool>(cols, false));
        vis[row][col] = true;
        int steps = 0;
        while(!q.empty()) {
            for (int i = q.size(); i > 0; i--) {
                auto cur = q.front();
                q.pop();
                row = cur.first;
                col = cur.second;
                if(grid[row][col] == 0) {
                    distance[row][col][0] += steps;
                    distance[row][col][1] += 1;
                }
                for(auto& [dr, dc]: dirs) {
                    int nextRow = row + dr;
                    int nextCol = col + dc;
                    if (nextRow >= 0 && nextCol >= 0 && nextRow < rows && nextCol < cols) {
                        if(!vis[nextRow][nextCol] && grid[nextRow][nextCol] == 0) {
                            vis[nextRow][nextCol] = true;
                            q.emplace(nextRow, nextCol);
                        }
                    }
                }
            }
            steps++;
        }
    }
};

Solution 3: Optimized BFS with Grid Modification

Time Complexity: O(m²n²) - For each building, BFS to all reachable empty lands
Space Complexity: O(mn) - For total distance tracking

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        const int rows = grid.size(), cols = grid[0].size();
        constexpr array<pair<int, int>, 4> dirs = \{\{\{1, 0\}, \{-1, 0\}, \{0, 1\}, \{0, -1\}\}\};
        int emptyLandValue =0, minDist = INT_MAX;
        vector<vector<int>> total(rows, vector<int> (cols, 0));
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if(grid[row][col] == 1) {
                    minDist = INT_MAX;
                    queue<pair<int, int>> q;
                    q.emplace(row, col);
                    int steps = 0;
                    while(!q.empty()) {
                        steps++;
                        for(int level = q.size(); level > 0; level--) {
                            auto cur = q.front();
                            q.pop();
                            for (auto& [dr, dc]: dirs) {
                                int nextRow = cur.first + dr;
                                int nextCol = cur.second + dc;
                                if(nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols
                                && grid[nextRow][nextCol] == emptyLandValue){
                                    grid[nextRow][nextCol]--;
                                    total[nextRow][nextCol] += steps;
                                    q.emplace(nextRow, nextCol);
                                    minDist = min(minDist, total[nextRow][nextCol]);
                                }
                            }
                        }
                    }
                    emptyLandValue--;
                }
            }
        }
        return minDist == INT_MAX ? -1 : minDist;
    }
};

Step-by-Step Example

Let’s trace through Solution 2 with grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]:

Step 1: Count total houses = 3

Step 2: BFS from each building

  • Building at (0,0): Updates distances to all reachable empty lands
  • Building at (0,4): Updates distances to all reachable empty lands
  • Building at (2,2): Updates distances to all reachable empty lands

Step 3: Check each empty land

  • Only empty lands reachable by all 3 buildings are considered
  • Find minimum total distance among valid positions

Result: Position (1,2) with total distance 7

Key Insights

  1. BFS Level Processing: Process each level of BFS to calculate distances correctly
  2. Reachability Check: Ensure all buildings can reach the chosen empty land
  3. Distance Accumulation: Sum distances from all buildings to each empty land
  4. Grid Optimization: Use grid modification to track reachability efficiently

Approach Comparison

Approach Pros Cons
Solution 1 Simple logic, easy to understand Less efficient, modifies original grid
Solution 2 Clean separation, tracks reachability Uses extra space for distance tracking
Solution 3 Most efficient, reuses grid space Complex logic, harder to debug

Common Mistakes

  • Incorrect Distance Calculation: Not using level-by-level BFS
  • Reachability Issues: Not checking if all buildings can reach empty land
  • Grid Modification: Modifying original grid without proper restoration
  • Boundary Conditions: Not handling edge cases properly