Leetcode #317: Shortest Distance from All Buildings
In this guide, we solve Leetcode #317 Shortest Distance from All Buildings in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
You are given an m x n grid grid of values 0, 1, or 2, where: each 0 marks an empty land that you can pass by freely, each 1 marks a building that you cannot pass through, and each 2 marks an obstacle that you cannot pass through. You want to build a house on an empty land that reaches all buildings in the shortest total travel distance.
Quick Facts
- Difficulty: Hard
- Premium: Yes
- Tags: Breadth-First Search, Array, Matrix
Intuition
We need level-by-level exploration or shortest steps, which is ideal for BFS.
A queue naturally models the frontier of the search.
Approach
Push initial nodes into a queue and expand in layers.
Track visited nodes to prevent cycles.
Steps:
- Initialize queue with start nodes.
- Process level by level.
- Track visited nodes.
Example
Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7
Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2).
The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal.
So return 7.
Python Solution
class Solution:
def shortestDistance(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
q = deque()
total = 0
cnt = [[0] * n for _ in range(m)]
dist = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
total += 1
q.append((i, j))
d = 0
vis = set()
while q:
d += 1
for _ in range(len(q)):
r, c = q.popleft()
for a, b in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
x, y = r + a, c + b
if (
0 <= x < m
and 0 <= y < n
and grid[x][y] == 0
and (x, y) not in vis
):
cnt[x][y] += 1
dist[x][y] += d
q.append((x, y))
vis.add((x, y))
ans = inf
for i in range(m):
for j in range(n):
if grid[i][j] == 0 and cnt[i][j] == total:
ans = min(ans, dist[i][j])
return -1 if ans == inf else ans
Complexity
The time complexity is O(V+E). The space complexity is O(V).
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.