LeetCode 317 - Shortest Distance from All Buildings

The problem asks us to find the optimal location to build a house on a grid so that the total travel distance to all existing buildings is minimized. The input is an m x n grid of integers where each cell is either empty land (0), a building (1), or an obstacle (2).

leetcodehardarraybreadth-first-searchmatrix

LeetCode Problem 317

Difficulty: 🔴 Hard
Topics: Array, Breadth-First Search, Matrix

Solution

Problem Understanding

The problem asks us to find the optimal location to build a house on a grid so that the total travel distance to all existing buildings is minimized. The input is an m x n grid of integers where each cell is either empty land (0), a building (1), or an obstacle (2). You can only move up, down, left, or right, so diagonal movements are not allowed. The goal is to identify an empty land cell such that the sum of distances to all buildings is the smallest possible, and return that sum. If no empty land can reach all buildings (for example, if obstacles block access), we return -1.

Constraints such as 1 <= m, n <= 50 suggest that brute-force solutions may be feasible but could be inefficient if not optimized. Each grid has at least one building, so we do not have to handle the case of a grid without buildings. Edge cases include grids with no empty land, grids where some buildings are isolated by obstacles, or grids with all obstacles around a building.

The key challenge is efficiently calculating distances from every empty land to all buildings without repeatedly traversing the same paths, which would be computationally expensive.

Approaches

A brute-force approach would attempt to start from every empty land, run a BFS or DFS to calculate the sum of distances to all buildings, and then pick the minimum. While this is correct, it is too slow for a 50x50 grid with many buildings because it performs O(m*n) BFS traversals, each taking O(m*n) time, resulting in O((m*n)^2) time complexity.

The optimal approach leverages BFS from each building instead of from empty land. By starting from buildings and propagating distances to reachable empty lands, we can efficiently track cumulative distances and the number of buildings each empty land can reach. This allows us to avoid redundant BFS traversals and quickly identify empty lands that are accessible from all buildings. The key insight is that each empty land must be reachable from every building, so by incrementally tracking reachable counts and distances, we can determine the minimum total distance efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O((m*n)^2) O(m*n) BFS from every empty land to all buildings, inefficient for larger grids
Optimal O(k_m_n) O(m*n) BFS from each building, accumulate distances and counts, k is number of buildings

Algorithm Walkthrough

  1. Initialize two matrices: distances to store cumulative distances from all buildings to each empty land, and reach to store how many buildings each empty land can reach.
  2. Count the total number of buildings in the grid.
  3. For each building, perform BFS:

a. Maintain a queue for BFS starting at the building.

b. Track the current distance from the building to empty lands.

c. For each empty land reached, update distances by adding the distance, and increment reach to mark that this building can reach it. 4. After BFS from all buildings, iterate through all empty lands:

a. If an empty land is reachable from all buildings (reach[i][j] == total_buildings), it is a candidate for the house.

b. Track the minimum cumulative distance among all candidates. 5. Return the minimum distance found. If no empty land can reach all buildings, return -1.

Why it works: By performing BFS from each building rather than from empty land, each distance from a building to an empty land is counted exactly once. The reach matrix ensures that we only consider empty lands accessible from every building. This guarantees that the returned distance is minimal and valid.

Python Solution

from collections import deque
from typing import List

class Solution:
    def shortestDistance(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return -1

        m, n = len(grid), len(grid[0])
        distances = [[0] * n for _ in range(m)]
        reach = [[0] * n for _ in range(m)]
        total_buildings = sum(val == 1 for row in grid for val in row)
        directions = [(0,1),(1,0),(0,-1),(-1,0)]

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    visited = [[False]*n for _ in range(m)]
                    queue = deque([(i,j,0)])
                    visited[i][j] = True
                    while queue:
                        x, y, dist = queue.popleft()
                        for dx, dy in directions:
                            nx, ny = x + dx, y + dy
                            if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] == 0:
                                visited[nx][ny] = True
                                distances[nx][ny] += dist + 1
                                reach[nx][ny] += 1
                                queue.append((nx, ny, dist + 1))

        min_distance = float('inf')
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0 and reach[i][j] == total_buildings:
                    min_distance = min(min_distance, distances[i][j])

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

Implementation Explanation: The code first calculates the total number of buildings and initializes matrices for distances and reach counts. For each building, BFS propagates distances to all reachable empty lands while updating cumulative distances and reachable counts. Finally, it scans the grid for empty lands reachable by all buildings, returning the minimal cumulative distance or -1 if none exists.

Go Solution

package main

import "container/list"

func shortestDistance(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    distances := make([][]int, m)
    reach := make([][]int, m)
    for i := range grid {
        distances[i] = make([]int, n)
        reach[i] = make([]int, n)
    }

    totalBuildings := 0
    directions := [][2]int{{0,1},{1,0},{0,-1},{-1,0}}

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                totalBuildings++
                visited := make([][]bool, m)
                for k := range visited {
                    visited[k] = make([]bool, n)
                }
                queue := list.New()
                queue.PushBack([3]int{i,j,0})
                visited[i][j] = true
                for queue.Len() > 0 {
                    elem := queue.Front()
                    queue.Remove(elem)
                    x, y, dist := elem.Value.([3]int)[0], elem.Value.([3]int)[1], elem.Value.([3]int)[2]
                    for _, d := range directions {
                        nx, ny := x + d[0], y + d[1]
                        if nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] == 0 {
                            visited[nx][ny] = true
                            distances[nx][ny] += dist + 1
                            reach[nx][ny]++
                            queue.PushBack([3]int{nx, ny, dist+1})
                        }
                    }
                }
            }
        }
    }

    minDistance := 1<<31 - 1
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 0 && reach[i][j] == totalBuildings {
                if distances[i][j] < minDistance {
                    minDistance = distances[i][j]
                }
            }
        }
    }

    if minDistance == 1<<31 - 1 {
        return -1
    }
    return minDistance
}

Go-specific Notes: We use container/list for BFS queues. The visited matrix is re-initialized for each building. 1<<31 - 1 represents infinity. Go requires explicit initialization of slices, unlike Python.

Worked Examples

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

After BFS from each building, distances and reach matrices become:

i,j distance reach
(1,2) 7 3

Other empty lands either cannot reach all buildings or have higher distance. Return 7.

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

Empty land (0,1) is reachable from one building with distance 1. Return 1.

Example 3: grid = [[1]]

No empty land exists. Return -1.

Complexity Analysis

Measure Complexity Explanation
Time O(k_m_n) BFS from each building, k is number of buildings, each BFS visits each empty land at most once
Space O(m*n) For distance and reach matrices and BFS visited matrix

The complexity is manageable since m,n <= 50 and `k <=