⚡Flashcard Drill➔
NeetCode #615LC-317HardGraphsNC Algo100
← Back to All Problems

#615 · #317 · Shortest Distance from All Buildings(离建筑物最近的距离)

📌 Problem Statement & Constraints

You are given an m x n grid where 0 is empty, 1 is a building and 2 is an obstacle. You want to build a house on an empty cell reachable from all buildings, minimising the total travel distance (Manhattan, avoiding obstacles). Return that minimum distance, or -1. Constraints: 1 <= m, n <= 50, at least one building.

💡 Core Algorithmic Approaches

  1. For each building, run a BFS over the empty cells, accumulating the distance to that building and counting how many buildings reach each cell.
  2. A cell is a candidate only when it is reached by all buildings.
  3. The answer is the minimum accumulated distance over the candidates.
  4. Each BFS is independent, so the total is O(buildings * m * n).

💻 Benchmark Python3 Implementation

class Solution:
    def shortestDistance(self, grid: List[List[int]]) -> int:
        from collections import deque
        m, n = len(grid), len(grid[0])
        total = [[0] * n for _ in range(m)]    # sum of distances to each building
        reached = [[0] * n for _ in range(m)]  # how many buildings reach this cell
        buildings = 0

        for i in range(m):
            for j in range(n):
                if grid[i][j] != 1:
                    continue
                buildings += 1
                q = deque([(i, j, 0)])
                seen = [[False] * n for _ in range(m)]
                seen[i][j] = True
                while q:
                    r, c, d = q.popleft()
                    for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                        nr, nc = r + dr, c + dc
                        if (0 <= nr < m and 0 <= nc < n and not seen[nr][nc]
                                and grid[nr][nc] == 0):   # only empty cells
                            seen[nr][nc] = True
                            total[nr][nc] += d + 1
                            reached[nr][nc] += 1
                            q.append((nr, nc, d + 1))

        best = float("inf")
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0 and reached[i][j] == buildings:
                    best = min(best, total[i][j])
        return best if best != float("inf") else -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(buildings * m * n): one BFS per building.
💾 Space Complexity
O(m * n) per BFS (reused across iterations).

⚠️ Interview Pitfalls & Follow-ups

  • Requiring reached == buildings: a cell reachable from only some buildings is invalid.
  • Allowing the BFS to pass through buildings or obstacles: only empty cells are traversable.
  • Using Manhattan distance directly: obstacles make the true distance larger.
  • Forgetting the seen array per BFS: the same cell could be enqueued repeatedly.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems