We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Distance from All Buildings

Number: 317

Difficulty: Hard

Paid? Yes

Companies: Meta, DoorDash, Google, TikTok, Bloomberg, Microsoft, Amazon, ByteDance, Snap, Zenefits

Problem Description

Given a grid where each cell represents an empty land (0), a building (1), or an obstacle (2), the goal is to find an empty land such that the sum of Manhattan distances from this land to all buildings is minimized. You can move only up, down, left, or right. Return the minimum sum of distances. If no such empty land exists that can reach all buildings, return -1.

Key Insights

  • We need to compute the Manhattan distance from each building (cell value 1) to all empty lands (cell value 0) by performing a BFS.
  • Maintain two matrices: one for cumulative total distances and another for the count of buildings that reached a particular empty cell.
  • Ensure that only those empty cells reachable by every building are considered.
  • The ideal cell will have a reach count equal to the total number of buildings.
  • If multiple buildings cannot all reach any specific empty cell, then return -1.

Space and Time Complexity

Time Complexity: O(k * m * n) where k is the number of buildings and m,n are the grid dimensions. Space Complexity: O(m * n) due to the auxiliary matrices and visited state tracking used in BFS.

Solution

We first iterate through the grid to locate all buildings while counting them. For each building, we perform a BFS to compute the shortest distance to each reachable empty cell. During the BFS, we update the cumulative distance for that cell and record that it was reached by one additional building. After processing all the buildings, we scan the grid to find the empty cell that is reachable from all buildings and has the minimum cumulative distance. If no such cell exists, we return -1.

Code Solutions

from collections import deque

def shortestDistance(grid):
    if not grid or not grid[0]:
        return -1

    m, n = len(grid), len(grid[0])
    total_buildings = 0
    total_distance = [[0] * n for _ in range(m)]
    reachable_count = [[0] * n for _ in range(m)]
    
    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 x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if 0 <= x < m and 0 <= y < n and not visited[x][y] and grid[x][y] == 0:
                    visited[x][y] = True
                    total_distance[x][y] += dist + 1
                    reachable_count[x][y] += 1
                    q.append((x, y, dist+1))
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                total_buildings += 1
                bfs(i, j)
    
    min_distance = float('inf')
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 0 and reachable_count[i][j] == total_buildings:
                min_distance = min(min_distance, total_distance[i][j])
    
    return min_distance if min_distance != float('inf') else -1

# Example test:
print(shortestDistance([[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]))
← Back to All Questions