Shortest Distance from All Buildings — LeetCode 317 Python Solution
HardLeetCode PremiumBreadth-First SearchArrayMatrix
- Problem
- #317
- Pattern
- Matrix and Grid
- Reading time
- 7 min
- Source
- leetcode.com
The problem
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.
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).
Python solution
Python
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 ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(V+E) |
| Space | O(V) auxiliary |
Pattern: Matrix and Grid
Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 317. Shortest Distance from All Buildings is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.
The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 317. Shortest Distance from All Buildings?
- LeetCode 317. Shortest Distance from All Buildings is rated Hard on LeetCode.
- What is the time complexity of LeetCode 317. Shortest Distance from All Buildings?
- The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 317. Shortest Distance from All Buildings?
- The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 317. Shortest Distance from All Buildings cover?
- LeetCode 317. Shortest Distance from All Buildings is tagged Breadth-First Search, Array and Matrix on LeetCode.
- Is LeetCode 317. Shortest Distance from All Buildings a premium problem?
- Yes. LeetCode 317. Shortest Distance from All Buildings is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.