Hard

Shortest Distance from All Buildings

LAB

Grid cells are 0 empty, 1 building, 2 obstacle. Return the minimum total distance from an empty cell to all buildings, or -1.

EXAMPLES

Example 1

Input
{
  "grid": [
    [
      1,
      0,
      2,
      0,
      1
    ],
    [
      0,
      0,
      0,
      0,
      0
    ],
    [
      0,
      0,
      1,
      0,
      0
    ]
  ]
}

Output
7

FUNCTION SHAPE

grid: intMatrix→int

SOLUTION NOTE

This is pretty interesting. The naive solution of BFS from every empty land cell to all the buildings is too slow and will TLE. We can reverse the problem, let's BFS from every building and update the min distance to every empty land cell. We maintain totalDist for this, as well as reach array representing how many buildings can be reached by this land cell. After the BFS, we collect the optimal empty.

Reveal reference solution +

pythonREFERENCE

def shortestDistance(self, grid):
    if not grid or not grid[0]:
        return -1
    m, n = len(grid), len(grid[0])
    totalDist = [[0] * n for _ in range(m)]
    reach = [[0] * n for _ in range(m)]
    buildingCount = sum(cell == 1 for row in grid for cell in row)

    def bfs(start_i, start_j):
        visited = [[False] * n for _ in range(m)]
        q = deque([(start_i, start_j, 0)])
        visited[start_i][start_j] = True

        while q:
            i, j, dist = q.popleft()
            for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
                ni, nj = i + dx, j + dy
                if 0 <= ni < m and 0 <= nj < n and not visited[ni][nj] and grid[ni][nj] == 0:
                    visited[ni][nj] = True
                    totalDist[ni][nj] += dist + 1
                    reach[ni][nj] += 1
                    q.append((ni, nj, dist + 1))

    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                bfs(i, j)

    result = float('inf')
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 0 and reach[i][j] == buildingCount:
                result = min(result, totalDist[i][j])

    return result if result != float('inf') else -1

TimeO(B * m * n)

SpaceO(m*n)

Open on LeetCode ↗