Leetcode: 317. Shortest Distance from All Buildings

Mistake: Overcomplicated solution. It would be easier to extract the Breadth-first search function.
Mistake: High constant factor in the implementation. Anything close to \(10^8\) needs heavy optimization in python.
Can we break-down the problem in small and easily to solve parts? Compute the distance from each house to an empty space and take the space that can be reached by all houses with the lower total distance. Time complexity is \(O(n^2 \times m^2)\) and space is \(O(n \times m)\).

from typing import List


class Solution:
    def shortestDistance(self, grid: List[List[int]]) -> int:
        N = len(grid)
        M = len(grid[0])
        dst = [[0] * M for _ in range(N)]
        cnt = [[0] * M for _ in range(N)]

        delta = [[+1, +0], [-1, +0], [+0, +1], [+0, -1]]

        def bfs(si, sj):
            vis = [[False] * M for _ in range(N)]
            queue = [(si, sj, 0)]
            for i, j, d in queue:
                dst[i][j] += d
                cnt[i][j] += 1
                for di, dj in delta:
                    ni = di + i
                    nj = dj + j
                    if 0 <= ni < N and 0 <= nj < M and not vis[ni][nj]:
                        vis[ni][nj] = True
                        if grid[ni][nj] == 0:
                            queue.append((ni, nj, d + 1))
                        elif grid[ni][nj] == 1:
                            cnt[ni][nj] += 1

        houses = 0
        for si in range(N):
            for sj in range(M):
                if grid[si][sj] == 1:
                    if cnt[si][sj] != houses:
                        return -1
                    houses += 1
                    bfs(si, sj)

        ans = float("inf")
        for i in range(N):
            for j in range(M):
                if grid[i][j] == 0 and cnt[i][j] == houses and ans > dst[i][j]:
                    ans = dst[i][j]

        return -1 if ans == float("inf") else ans


assert (
    Solution().shortestDistance([[1, 0, 2, 0, 1], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0]])
    == 7
)
assert Solution().shortestDistance([[1, 0]]) == 1
assert Solution().shortestDistance([[1]]) == -1