Problem statement

https://leetcode.com/problems/shortest-distance-from-all-buildings/

Solution

If we check distances from each empty point to buildings we will have $O(m^2n^2)$ complexity. If we do at opposite way: for every of $k$ building built $m\times n$ matrix of distances, then sum them. Here is straightforward implementation, we need to be careful with cases such that some cell is not reachible during dfs. To make it faster we can do some prunnings.

Complexity

Time complexity is $O(mnk)$, where $k$ is number of buildings, space complexity is $O(mn)$.

Code

class Solution:
    def shortestDistance(self, grid):
        m, n = len(grid), len(grid[0])
        
        def bfs(grd, x, y):
            queue = deque([(0, x, y)])
            while queue:
                dist, r, c = queue.popleft()
                for dr, dc in [(r, c+1), (r, c-1), (r-1, c), (r+1, c)]:
                    if 0 <= dr < m and 0 <= dc < n and grd[dr][dc] == 0:
                        grd[dr][dc] = dist + 1
                        queue.append((dist + 1, dr, dc))
            
            return grd
        
        total = [[0] * n for _ in range(m)]
        
        for x, y in product(range(m), range(n)):
            if grid[x][y] != 1: continue
                
            grd = [x[:] for x in grid]
            q = bfs(grd, x, y)
            for i,j in product(range(m), range(n)):
                if q[i][j] == 0: q[i][j] = float("inf")
                total[i][j] += q[i][j]
        
        cands = [total[x][y] for x, y in product(range(m), range(n)) if grid[x][y] == 0]
        if not cands or min(cands) == float("inf"): return -1
        return min(cands)