Practice/DoorDash/Leetcode 317. Shortest Distance from All Buildings

Leetcode 317. Shortest Distance from All Buildings

CodingMust

Problem

You are given a 2D grid representing a city map where:

• 1 represents a building
• 0 represents empty land where you can place a meeting point
• 2 represents an obstacle that cannot be traversed

Your task is to find an empty land cell that minimizes the total walking distance for all people coming from different buildings. The walking distance is measured as Manhattan distance (you can only move up, down, left, or right).

Return the minimum total distance. If it's impossible to find such a location that is reachable from all buildings, return -1.

Requirements

1. Find an empty cell (marked as 0) that can be reached from all buildings
2. Calculate the sum of shortest path distances from all buildings to that cell
3. Return the minimum sum among all valid empty cells
4. Obstacles (2) block paths and cannot be traversed
5. If no empty cell can reach all buildings, return -1

Constraints

• 1 <= grid.length, grid[0].length <= 50
• grid[i][j] is either 0, 1, or 2
• There will be at least one building in the grid
• Time complexity should be optimized for the grid size
• Space complexity: O(rows × cols)

Examples

Example 1:

Input: grid = [[1,0,2,0,1], [0,0,0,0,0], [0,0,1,0,0]] Output: 7 Explanation: The cell at position (1,2) can reach all three buildings. Distance from building at (0,0): 3 steps Distance from building at (0,4): 2 steps Distance from building at (2,2): 2 steps Total: 3 + 2 + 2 = 7

Example 2:

Input: grid = [[1,0,2], [2,2,2], [0,0,1]] Output: -1 Explanation: The obstacle wall at row 1 completely separates the buildings, making it impossible for any empty cell to reach all buildings.

Example 3:

Input: grid = [[1,0],[0,0]] Output: 1 Explanation: The cell at (0,1) or (1,0) are both optimal with distance 1.