317. Shortest Distance from All Buildings - Detailed Explanation

Problem Statement

You are given a 2D grid where each cell can be:

• 0: Empty land
• 1: A building
• 2: An obstacle

Your task is to find an empty land cell such that the sum of the Manhattan distances from this cell to all the buildings is minimized. The Manhattan distance between two points (i, j) and (k, l) is calculated as |i - k| + |j - l|.

If it is not possible for any empty cell to reach all buildings (due to obstacles or isolation), return -1.

Example 1

Input:

grid = [
  [1, 0, 2, 0, 1],
  [0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0]
]

Output: 7

Explanation:

• There are 3 buildings located at (0,0), (0,4), and (2,2).
• The empty cell at (1,2) is optimal:
  • Distance to (0,0): |1-0| + |2-0| = 1 + 2 = 3
  • Distance to (0,4): |1-0| + |2-4| = 1 + 2 = 3
  • Distance to (2,2): |1-2| + |2-2| = 1 + 0 = 1
• Total distance = 3 + 3 + 1 = 7

Example 2

Input:

grid = [
  [1, 0],
  [0, 1]
]

Output: -1

Explanation: There is no empty cell that can reach both buildings due to their positions or intervening obstacles.

Constraints

• The grid dimensions (m x n) can vary.
• The grid contains a mix of buildings, empty lands, and obstacles.
• Efficiency is key, as the grid can be moderately large and many buildings might be present.

Hints

1. Breadth-First Search (BFS):

   • Instead of checking every empty cell, consider running BFS from each building. This will allow you to propagate distances outward from each building.

2. Distance and Reach Accumulation:

   • Use two auxiliary matrices:
     • distances: To accumulate the sum of distances from all buildings to each empty cell.
     • reach: To count how many buildings can reach a given empty cell.

3. Final Decision:

   • After processing all buildings, examine each empty cell (value 0) that is reachable from all buildings (i.e. its reach equals the total number of buildings). Return the minimum distance sum among these cells.

Approaches

Approach 1: Brute Force (Inefficient)

• Idea:
  • For every empty cell, perform a BFS or DFS to compute the distance from that cell to every building.
• Downside:
  • Repeated searches from every empty cell lead to high computational costs (O(m*n*(m*n)) in worst-case scenarios).

Approach 2: Multi-Source BFS from Each Building (Optimal)

• Idea:
  • Perform a BFS from each building. During each BFS, update two matrices:
    • distances[i][j]: The cumulative distance sum from all buildings that can reach cell (i, j).
    • reach[i][j]: The count of buildings that can reach cell (i, j).
• Process:
  1. Count the total number of buildings in the grid.
  2. For each building, perform a BFS to compute and update distances for all reachable empty cells.
  3. After processing, iterate over every empty cell. If an empty cell is reached from all buildings (i.e. reach[i][j] == totalBuildings), consider its cumulative distance.
  4. Return the minimum distance found. If no cell meets the criteria, return -1.
• Time Complexity:
  • Each building's BFS runs in O(m*n) and if there are B buildings, overall complexity is O(B * m * n).

Step-by-Step Walkthrough and Visual Example

Consider the grid:

[
  [1, 0, 2, 0, 1],
  [0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0]
]

1. Initialization:

   • Total number of buildings = 3.
   • Create two matrices distances and reach (size equal to the grid), filled with 0s.

2. BFS from Each Building:

   • For the building at (0,0):
     • Start a BFS, updating reachable empty cells with their distance from (0,0).
   • Repeat the BFS for buildings at (0,4) and (2,2).

3. Accumulate and Evaluate:

   • After all BFS runs, each empty cell contains:
     • The total distance from all buildings that could reach it.
     • A count of how many buildings reached it.
   • Only consider cells where the reach count equals 3 (all buildings). Among these, select the cell with the minimum distance sum. In our example, the cell (1,2) gives a sum of 7.

Code Implementation

Python Code