LeetCode 317: Shortest Distance from All Buildings Solution in Python – A Step-by-Step Guide

What Is LeetCode 317: Shortest Distance from All Buildings?

In LeetCode 317: Shortest Distance from All Buildings, you’re given a 2D grid where 0s are empty lands, 1s are buildings, and 2s are obstacles. Your goal is to find an empty land cell (0) that minimizes the total Manhattan distance to all buildings (1s), returning this minimum distance. For example, in a grid [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]], the best spot yields a total distance of 7. This problem tests your ability to compute distances in a constrained grid, building on concepts from LeetCode 286: Walls and Gates.

Problem Statement

• Input: A 2D integer grid (0=empty, 1=building, 2=obstacle).
• Output: An integer—the minimum total Manhattan distance from an empty cell to all buildings, or -1 if impossible.
• Rules:
• Manhattan distance: |x1-x2| + |y1-y2|.
• Must reach all buildings from the chosen cell.
• Moves are up, down, left, right (no diagonals).

Constraints

• 1 <= grid.length, grid[0].length <= 50
• grid[i][j] is 0, 1, or 2
• At least one building (1)

Examples

• Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
• Output: 7 (Best spot at (1,2): distances 1+3+3)
• Input: [[1,0]]
• Output: 1 (Only spot at (0,1))
• Input: [[1,2,0]]
• Output: 1

Understanding the Problem: Finding the Optimal Spot

To solve LeetCode 317: Shortest Distance from All Buildings in Python, we need to find an empty cell that minimizes the sum of Manhattan distances to all buildings, ensuring all are reachable. A naive approach—checking each empty cell with BFS to every building—is O(mnkB), where mn is grid size, k is empty cells, and B is buildings—too slow. Instead, we’ll use:

• Best Solution (BFS from Buildings): O(m*n*B) time, O(m*n) space—efficient and scalable.
• Alternative Solution (BFS from Empty Lands): O(m*n*k) time, O(m*n) space—intuitive but slower.

Let’s start with the BFS-from-buildings solution, explained in a beginner-friendly way.

Best Solution: BFS from Each Building

Why This Is the Best Solution

The BFS-from-buildings approach is the top choice for LeetCode 317 because it’s efficient—O(mnB) time, O(m*n) space—and cleverly aggregates distances by traversing from each building once. It uses BFS to compute distances to all reachable cells, then sums these at each empty spot, ensuring all buildings contribute. It’s like sending out scouts from each building to map the city—smart and fast!

How It Works

Think of this as a distance overlay:

• Step 1: Count Buildings and Initialize:
• Track number of buildings.
• Use grids for total distance and reachability count.
• Step 2: BFS from Each Building:
• For each building, run BFS to compute distances to all reachable empty cells.
• Update total distance and count of buildings reached per cell.
• Step 3: Find Minimum:
• Among cells reached by all buildings, pick the smallest total distance.
• Step 4: Why It Works:
• Aggregates distances efficiently.
• Ensures all buildings are considered.

It’s like mapping the city from every building’s perspective!

Step-by-Step Example

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

• Buildings: (0,0), (0,4), (2,2), Count = 3
• Init: Distance = [[0]*5]*3, Reach = [[0]*5]*3
• BFS from (0,0):
• (0,1): 1, (1,0): 1, (1,1): 2, etc.
• Distance[1][2] += 3, Reach[1][2] += 1
• BFS from (0,4):
• Distance[1][2] += 3, Reach[1][2] += 1
• BFS from (2,2):
• Distance[1][2] += 1, Reach[1][2] += 1
• Result: (1,2) reached by 3, total = 7, Min = 7

Code with Detailed Line-by-Line Explanation

Copy codefrom collections import deque

class Solution:
    def shortestDistance(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return -1

        m, n = len(grid), len(grid[0])
        buildings = 0
        distance = [[0] * n for _ in range(m)]  # Total distance to buildings
        reach = [[0] * n for _ in range(m)]     # Buildings reached
        directions = [(0,1), (0,-1), (1,0), (-1,0)]

        # Count buildings and run BFS
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    buildings += 1
                    queue = deque([(i, j, 0)])
                    visited = set([(i, j)])
                    while queue:
                        r, c, dist = queue.popleft()
                        for dr, dc in directions:
                            nr, nc = r + dr, c + dc
                            if (0 <= nr < m and 0 <= nc < n and 
                                grid[nr][nc] == 0 and (nr, nc) not in visited):
                                distance[nr][nc] += dist + 1
                                reach[nr][nc] += 1
                                visited.add((nr, nc))
                                queue.append((nr, nc, dist + 1))

        # Find minimum distance
        min_dist = float('inf')
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0 and reach[i][j] == buildings:
                    min_dist = min(min_dist, distance[i][j])

        return min_dist if min_dist != float('inf') else -1

• Lines 5-6: Handle empty grid.
• Lines 8-11: Initialize grid size, counters, and directions.
• Lines 14-28: BFS from each building:
• Increment building count.
• Queue tracks (row, col, distance).
• Update distance and reach for empty cells.
• Lines 31-35: Find min distance among fully reachable cells.
• Time Complexity: O(m*n*B)—BFS per building.
• Space Complexity: O(m*n)—grids and queue.

This is like a city distance mapper—swift and thorough!

Alternative Solution: BFS from Each Empty Land

Why an Alternative Approach?

The BFS-from-empty-lands approach also works—O(mnk) time, O(m*n) space—by running BFS from each empty cell to count buildings and sum distances. It’s more intuitive but slower due to more BFS runs. It’s like exploring from every park spot—straightforward but exhaustive!

How It Works

Explore from empty cells:

• Step 1: Identify empty lands and buildings.
• Step 2: BFS from each empty cell:
• Compute total distance to all buildings.
• Step 3: Pick minimum distance.

Step-by-Step Example

Example: grid = [[1,0],[0,1]]

• Empty: (0,1), (1,0)
• BFS from (0,1): Dist to (0,0)=1, (1,1)=1, Total = 2
• BFS from (1,0): Dist to (0,0)=1, (1,1)=1, Total = 2
• Result: Min = 2

Code for Alternative Approach

Copy codefrom collections import deque

class Solution:
    def shortestDistance(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        buildings = sum(row.count(1) for row in grid)
        directions = [(0,1), (0,-1), (1,0), (-1,0)]

        def bfs(r, c):
            queue = deque([(r, c, 0)])
            visited = {(r, c)}
            total_dist, reached = 0, 0
            while queue:
                row, col, dist = queue.popleft()
                if grid[row][col] == 1:
                    total_dist += dist
                    reached += 1
                    continue
                for dr, dc in directions:
                    nr, nc = row + dr, col + dc
                    if (0 <= nr < m and 0 <= nc < n and 
                        grid[nr][nc] != 2 and (nr, nc) not in visited):
                        visited.add((nr, nc))
                        queue.append((nr, nc, dist + 1))
            return total_dist if reached == buildings else float('inf')

        min_dist = float('inf')
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    min_dist = min(min_dist, bfs(i, j))

        return min_dist if min_dist != float('inf') else -1

• Time Complexity: O(m*n*k)—k empty cells.
• Space Complexity: O(m*n)—queue and visited.

It’s a thorough distance checker!

Comparing the Two Solutions

• BFS from Buildings (Best):
• Pros: O(m*n*B) time, O(m*n) space, fewer BFS runs.
• Cons: Aggregates need care.
• BFS from Empty (Alternative):
• Pros: O(m*n*k) time, O(m*n) space, simpler logic.
• Cons: Slower with many empty cells.

Buildings-first wins for efficiency.

Additional Examples and Edge Cases

• [[1]]: -1 (No empty).
• [[1,2,1]]: -1 (No path).
• [[0,1]]: 1.

Both handle these correctly.

Complexity Breakdown

• BFS from Buildings: Time O(m*n*B), Space O(m*n).
• BFS from Empty: Time O(m*n*k), Space O(m*n).

Buildings-first is faster with fewer BFS runs.

Key Takeaways

• BFS from Buildings: Aggregate smartly—efficient!
• BFS from Empty: Explore all—clear!
• Python: Queues and grids rock—see [Python Basics](/python/basics).
• Grids: Distance puzzles are fun.

Final Thoughts: Plan the Perfect Spot

LeetCode 317: Shortest Distance from All Buildings in Python is a grid-based optimization gem. BFS from buildings offers speed and elegance, while BFS from empty lands provides a direct approach. Want more grid challenges? Try LeetCode 286: Walls and Gates or LeetCode 1091: Shortest Path in Binary Matrix. Ready to measure? Head to Solve LeetCode 317 on LeetCode (premium) and find that optimal distance today!