Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 317. Shortest Distance from All Buildings

Given a grid with buildings (1), empty land (0), and obstacles (2), find an empty cell that minimizes the sum of shortest (Manhattan) path distances from all buildings while avoiding obstacles; return that minimum sum or -1 if no empty cell is reachable from every building. This problem primarily requires repeated BFS distance accumulation and reachability checks from each building to identify the globally optimal empty location.

Asked at:

Doordash

DESCRIPTION

Input:

grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

Output:

Explanation: The optimal meeting point is at cell (1,2). The distances from the three buildings at (0,0), (0,4), and (2,2) are 3, 3, and 1 respectively, giving a total of 7.

Constraints:

1 <= grid.length, grid[0].length <= 50
grid[i][j] is either 0, 1, or 2
There will be at least one building in the grid
Distance is calculated using Manhattan distance (|x1 - x2| + |y1 - y2|)

Understanding the Problem

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?

Brute Force Approach

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.

Visualization

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

Start: 3x5 grid. Find empty cell minimizing total distance to all buildings.

0 / 3680

Test Your Knowledge

Complexity Analysis

Time Complexity: O(m²n² × B) For each of O(mn) empty cells, we perform BFS that visits O(mn) cells, and we need to find B buildings. With B buildings, this becomes O(m²n² × B) in the worst case.

Space Complexity: O(mn) BFS queue can hold O(mn) cells in the worst case when the grid is mostly empty

Building Intuition

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:

Accumulate distances: Add each building's distance contribution to every reachable empty cell
Track reachability: Count how many buildings can reach each empty cell
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).

Common Mistakes

Starting BFS from empty cells instead of buildings - this leads to O(m²n²) complexity when there are many empty cells but few buildings

Forgetting to check reachability - an empty cell might accumulate distances from some buildings but not be reachable from all buildings, making it invalid

Not handling obstacles correctly in BFS - obstacles block paths and should not be added to the queue or marked as visited

Using Euclidean distance instead of Manhattan distance - the problem specifically requires Manhattan distance (no diagonal movement)

Integer overflow when accumulating distances - with large grids and many buildings, distance sums can grow large, so use appropriate data types

Optimal Solution

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).

Visualization

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

Start: Find empty cell minimizing sum of distances from all buildings

0 / 728

Test Your Knowledge

Complexity Analysis

Time Complexity: O(B × mn) We perform BFS from each of B buildings, and each BFS visits at most O(mn) cells. With B buildings, total time is O(B × mn), which is much better than the brute force when B << number of empty cells.

Space Complexity: O(mn) We maintain two auxiliary grids (distance accumulation and reachability count) of size O(mn), plus the BFS queue which is O(mn) in the worst case

What We've Learned

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.

Test Your Understanding

Why is matrix the right data structure for this problem?

matrix provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid November, 2025

Amazon

Senior

Early September, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 317. Shortest Distance from All Buildings

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact