Leetcode 317. Shortest Distance from All Buildings

Let's understand what we're being asked to do. We have a 2D grid where each cell can be:

• 1 = a building
• 0 = empty land (potential meeting point)
• 2 = an obstacle (cannot pass through)

We need to find an empty cell (0) that minimizes the total walking distance from all buildings. Distance is measured using Manhattan distance (only horizontal and vertical moves, no diagonals).

Example walkthrough: Given grid [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]], we have buildings at positions (0,0), (0,4), and (2,2). We need to check each empty cell and calculate the sum of distances from all three buildings. The cell with the minimum total distance is our answer.

Critical constraint: The empty cell must be reachable from every building. If any building cannot reach a particular empty cell (blocked by obstacles), that cell is not a valid meeting point.

Edge cases to consider: What if no empty cell can reach all buildings? (return -1). What if there are no buildings? What if the grid has no empty cells?

For each empty cell in the grid, perform a BFS to calculate the sum of distances to all buildings. Check if the empty cell can reach every building (if not, skip it). Track the minimum distance sum across all valid empty cells. This approach is straightforward but inefficient because we repeat BFS from potentially many empty cells, and each BFS explores the entire grid.

from collections import deque
def shortest_distance(grid):
    """
    Brute force: For each empty cell, BFS to all buildings.
    Returns minimum total distance or -1 if unreachable.
    """
    if not grid or not grid[0]:
        return -1
    
    rows, cols = len(grid), len(grid[0])
    
    # Find all buildings and empty cells
    buildings = []
    empty_cells = []
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                buildings.append((r, c))
            elif grid[r][c] == 0:
                empty_cells.append((r, c))
    
    if not buildings or not empty_cells:
        return -1
    
    min_distance = float('inf')
    
    # Try each empty cell as potential meeting point
    for empty_r, empty_c in empty_cells:
        total_distance = 0
        reachable_buildings = 0
        
        # BFS from this empty cell to all buildings
        for building_r, building_c in buildings:
            # BFS to find distance to this building
            queue = deque([(empty_r, empty_c, 0)])
            visited = set()
            visited.add((empty_r, empty_c))
            found = False
            
            while queue:
                curr_r, curr_c, dist = queue.popleft()
                
                # Check if reached this building
                if curr_r == building_r and curr_c == building_c:
                    total_distance += dist
                    reachable_buildings += 1
                    found = True
                    break
                
                # Explore 4 directions
                for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                    new_r, new_c = curr_r + dr, curr_c + dc
                    
                    if (0 <= new_r < rows and 0 <= new_c < cols and
                        (new_r, new_c) not in visited and
                        grid[new_r][new_c] != 2):
                        visited.add((new_r, new_c))
                        queue.append((new_r, new_c, dist + 1))
            
            # If couldn't reach this building, skip this empty cell
            if not found:
                break
        
        # Check if this empty cell can reach all buildings
        if reachable_buildings == len(buildings):
            min_distance = min(min_distance, total_distance)
    
    return min_distance if min_distance != float('inf') else -1

Instead of starting from each empty cell and searching for all buildings (which would be inefficient), we can reverse the perspective: start from each building and calculate distances to all reachable empty cells.

For each building, we explore outward level-by-level, recording the distance to each empty cell we can reach. This naturally gives us shortest paths due to the level-by-level exploration pattern.

By exploring from each building separately, we can:

1. Accumulate distances: Add each building's distance contribution to every reachable empty cell
2. Track reachability: Count how many buildings can reach each empty cell
3. Filter invalid cells: Only consider cells reachable by ALL buildings

This transforms the problem from checking every cell-to-all-buildings into a more efficient building-to-all-cells approach.

Imagine you have 3 friends living in different buildings, and you want to find a park (empty cell) to meet.

Instead of checking every park and measuring distances to all 3 friends, each friend explores outward from their building, marking distances to every park they can reach. After all 3 friends finish exploring:

• Parks that all 3 friends marked are valid meeting points
• For each valid park, sum up the 3 distance values
• The park with the minimum total is optimal

This approach naturally handles obstacles (friends can't pass through them) and unreachable areas (some parks might not be marked by all friends).

Reverse the search direction: perform BFS from each building (not from each empty cell). For each building, explore outward level-by-level, accumulating distances to all reachable empty cells. Maintain two auxiliary grids: one to accumulate total distances, and one to count how many buildings can reach each cell. After processing all buildings, scan the distance grid to find the minimum sum among cells reachable by all buildings. This approach is optimal because we only perform BFS once per building (typically much fewer than empty cells).

from collections import deque
def shortest_distance(grid):
    """
    Find empty cell minimizing sum of distances from all buildings.
    Uses multi-source BFS from each building to accumulate distances.
    """
    if not grid or not grid[0]:
        return -1
    
    rows, cols = len(grid), len(grid[0])
    building_count = sum(row.count(1) for row in grid)
    
    # Track total distance and reachability for each cell
    total_distance = [[0] * cols for _ in range(rows)]
    reachable_count = [[0] * cols for _ in range(rows)]
    
    buildings_processed = 0
    
    # Process each building with BFS
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                buildings_processed += 1
                
                # BFS from this building
                queue = deque([(r, c, 0)])
                visited = [[False] * cols for _ in range(rows)]
                visited[r][c] = True
                
                while queue:
                    curr_r, curr_c, dist = queue.popleft()
                    
                    # Explore 4 directions
                    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                        nr, nc = curr_r + dr, curr_c + dc
                        
                        # Check bounds and validity
                        if 0 <= nr < rows and 0 <= nc < cols:
                            if not visited[nr][nc] and grid[nr][nc] == 0:
                                visited[nr][nc] = True
                                
                                # Accumulate distance to this empty cell
                                total_distance[nr][nc] += dist + 1
                                reachable_count[nr][nc] += 1
                                
                                # Continue BFS
                                queue.append((nr, nc, dist + 1))
    
    # Find minimum distance among cells reachable by all buildings
    min_distance = float('inf')
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 0 and reachable_count[r][c] == building_count:
                min_distance = min(min_distance, total_distance[r][c])
    
    return min_distance if min_distance != float('inf') else -1

• Multi-source BFS pattern: When you need to find optimal locations relative to multiple sources (buildings), run BFS from each source separately and accumulate results in shared distance/count matrices - this is more intuitive than reverse BFS and naturally handles reachability constraints.
• Reachability tracking with counters: Use a visit counter matrix to track how many buildings can reach each empty cell - only cells where `visitCount[i][j] == totalBuildings` are valid candidates, elegantly filtering unreachable locations without complex set operations.
• Distance accumulation technique: Maintain a cumulative distance matrix where each BFS adds its distances to existing values - after all BFS runs complete, valid cells contain the total distance sum from all buildings, enabling O(1) final answer lookup.
• Early termination optimization: If any building's BFS cannot reach at least one empty cell that was reachable by previous buildings, return -1 immediately - this prevents wasting computation when no solution exists and catches the edge case efficiently.
• Grid traversal state management: For multi-pass grid algorithms, use separate matrices for different metrics (distances, visit counts, obstacles) rather than encoding everything in one matrix - this prevents state corruption and makes the logic clearer to debug.
• Facility location problem pattern: This multi-criteria grid optimization approach (minimize sum of distances while satisfying reachability constraints) extends to warehouse placement, emergency service location, and network node positioning problems in computational geometry.