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.

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

Thinking Process

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
Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Queue BFS (this problem) O(n) O(n) Shortest path in unweighted graphs
Multi-source BFS O(n) O(n) Start from all sources simultaneously
0-1 BFS / deque O(n) O(n) Weights 0 or 1
Level-order BFS O(n) O(w) Process by depth/layer

Solution

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(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;

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

        int minDistance = Integer.MAX_VALUE;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == 0) {
                    minDistance = Math.min(minDistance, bfs(grid, r, c, totalHouses));
                }
            }
        }

        return (minDistance == Integer.MAX_VALUE) ? -1 : minDistance;
    }
        public int bfs(int[][] grid, int startRow, int startCol, int totalHouses) {
        int[][] directions = new int[][] {
            new int[] {1, 0}, new int[] {-1, 0}, new int[] {0, 1}, new int[] {0, -1}
        };
        int rows = grid.length;
        int cols = grid[0].length;

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

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

        boolean[][] visited(rows, boolean[](cols, false));
        visited[startRow][startCol] = true;

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

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

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

                for (var e : directions.entrySet()) {
                    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 Integer.MAX_VALUE;
        }

        return distanceSum;
    }
}

Solution Explanation

Approach: Queue BFS (this problem)

Key idea: There are three main approaches to solve this problem:

How the code works:

  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

Walkthrough — input grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]], expected output 7:

The optimal location is (1,2) with total distance 7.

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

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

References

Key Takeaways

  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