NUHMAN.com

Introduction

LeetCode 317: Shortest Distance from All Buildings requires us to find the shortest distance from an empty land cell to all buildings in a grid. The grid consists of empty land (0), buildings (1), and obstacles (2). The task is to compute the shortest distance from every empty land cell to all buildings and return the minimum of these distances.

A key challenge in this problem is that we need to find the shortest distance from multiple buildings to each empty land cell, which can be achieved using multi-source breadth-first search (BFS).

Problem Statement

You are given a m x n grid where:

• Each cell can be one of the following:
• 0 representing empty land.
• 1 representing a building.
• 2 representing an obstacle.

The task is to find an empty land cell such that the sum of the shortest distances from this cell to all buildings is minimized.

Input:

• A m x n grid.

Output:

• The minimum distance from the empty land to all buildings.
• If there is no such empty land cell, return -1.

Example

python

# Example 1
Input: grid = [[1,0,2,0,1], [0,0,0,0,0], [1,0,2,0,1]]
Output: 7

# Example 2
Input: grid = [[1,0,1], [0,0,0], [1,0,1]]
Output: 4

# Example 3
Input: grid = [[1,0,0,0]]
Output: -1

Step-by-Step Solution

🧠 Intuition

We need to calculate the shortest distance from each empty land cell to all buildings in the grid. Since multiple buildings contribute to the distance, it’s efficient to perform multi-source BFS from all buildings simultaneously. This will help to explore the grid level by level, computing distances from each building to the surrounding cells.

✅ Approach

1. Multi-source BFS:
2. Start a BFS from every building (cell with 1). For each building, we traverse the grid and update the distance to each reachable empty land cell (0). We track the cumulative distance to all buildings for each cell.
3. Track Distance and Reach:
4. As we perform BFS, we maintain two matrices:

• distance[i][j]: This matrix holds the total distance from all buildings to the cell (i, j).
• reach[i][j]: This matrix tracks the number of buildings that can reach the cell (i, j).

1. Calculate the Minimum Distance:
2. After performing BFS for all buildings, the result will be the minimum value in the distance matrix where the reach matrix equals the total number of buildings. If no such cell exists, return -1.

✅ Python Code

python

from collections import deque

class Solution:
    def shortestDistance(self, grid: list[list[int]]) -> int:
        if not grid:
            return -1
        
        m, n = len(grid), len(grid[0])
        distance = [[0] * n for _ in range(m)]
        reach = [[0] * n for _ in range(m)]
        building_count = sum(grid[i][j] == 1 for i in range(m) for j in range(n))
        
        def bfs(start_i, start_j):
            visited = [[False] * n for _ in range(m)]
            queue = deque([(start_i, start_j, 0)])  # (i, j, dist)
            visited[start_i][start_j] = True
            
            while queue:
                i, j, dist = queue.popleft()
                
                # Explore the 4 possible directions
                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
                        queue.append((x, y, dist + 1))
                        distance[x][y] += dist + 1
                        reach[x][y] += 1
        
        # Run BFS from all buildings
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    bfs(i, j)
        
        # Find the minimum distance where all buildings can reach that cell
        min_distance = float('inf')
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0 and reach[i][j] == building_count:
                    min_distance = min(min_distance, distance[i][j])
        
        return min_distance if min_distance != float('inf') else -1

Explanation of the Code

1. Matrix Initialization:
2. We create two matrices:

• distance[i][j]: Stores the total distance to all buildings for the cell (i, j).
• reach[i][j]: Stores the number of buildings that can reach the cell (i, j).

1. BFS Function:
2. The BFS function (bfs) is initiated from each building's position and explores the grid. For each reachable empty land cell (0), we update its distance from the current building and increment the count in the reach matrix.
3. BFS from All Buildings:
4. We iterate through the grid and for each building, call the bfs function to propagate distances to all reachable empty land cells.
5. Result Calculation:
6. After processing all buildings, we iterate through the grid to find the minimum distance for cells that can be reached by all buildings (i.e., those with reach[i][j] == building_count). If no such cell exists, return -1.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(m * n * B)Space ComplexityO(m * n)

• Time Complexity:
• The BFS for each building visits each cell at most once. The total number of BFS operations is proportional to the number of buildings (B), and for each BFS, we visit each grid cell, resulting in a time complexity of O(m * n * B), where m and n are the grid dimensions, and B is the number of buildings.
• Space Complexity:
• We use auxiliary matrices distance and reach, each of size m * n, so the space complexity is O(m * n).

🔍 Edge Cases

1. No Buildings:
2. If there are no buildings in the grid, the result is -1 since there’s no point to calculate the distance.
3. All Cells are Obstacles:
4. If all cells are obstacles (2), there will be no empty land cells (0), and the result should be -1.
5. Only One Building:
6. If there's only one building, the result is the shortest distance to the closest empty land cell. If no empty land cells are present, the result should be -1.
7. Disconnected Buildings:
8. If the buildings are disconnected and there's no single empty land cell that can be reached by all buildings, the result should be -1.

✅ Conclusion

LeetCode 317: Shortest Distance from All Buildings is a challenging problem that requires efficiently computing the minimum distance from an empty land cell to all buildings in a grid. By using multi-source BFS, we can achieve this in a time complexity of O(m * n * B). This approach ensures that we efficiently compute the distances while handling multiple buildings and obstacles in the grid.