317. Shortest Distance from All Buildings

Problem Description

The problem involves finding the optimal location to build a house on a grid where there are empty lands, buildings, and obstacles. The grid contains cells marked as 0 for empty land, 1 for buildings, and 2 for obstacles. The task is to find an empty cell ('0') to build a house such that the total Manhattan Distance from that house to all buildings on the grid is minimized. The Manhattan Distance between two points (p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|, which allows movement only in the horizontal and vertical directions (no diagonals). If it is not possible to find such a location that reaches all buildings, the function should return -1.

Of note, we must respect the rules:

We cannot pass through buildings (1).
We cannot pass through obstacles (2).

The aim is to find an empty land (0) with the shortest total distance to all buildings, which signifies the best location for building the house.

Intuition

To solve this problem, we need to examine the distances between all the possible empty land spots and every building on the grid to determine the total travel distances for each location. This problem can be approached by using the Breadth-First Search (BFS) algorithm.

The BFS algorithm is suitable for finding the shortest path in a grid-based problem since it explores all neighbor vertices at the present depth before moving on to vertices at the next depth level.

Here's the high-level intuition behind the solution:

Starting at each building, perform a BFS to compute the distance of each reachable empty land space from the building.
Accumulate the distances and the number of paths reaching every empty land space during the BFS.
After performing BFS from all buildings, examine each empty land space to find the one with the shortest accumulated distance reached by all buildings.
If no such empty land space exists that can be reached by all the buildings, return -1.

The key insight is that to minimize the total travel distance, one needs to find an empty land space that is reachable by the most number of buildings and has the lowest summed distance to all of them.

Learn more about Breadth-First Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1dp[i] = dp[i] + dp[i - 1]dp[i] = (dp[i] + dp[j] + 1) for j in 0 to idp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know

Solution Approach

The given Python solution applies a BFS strategy for every building found on the grid to calculate the total distance of each empty land space from the building and keep track of the empty spaces that have been reached.

Here's a step-by-step breakdown of the solution:

Grid Initialization: First, we initialize the necessary grids: cnt to track the number of buildings that can reach a particular empty land, and dist to keep the accumulative distance of each empty land from all buildings.
BFS Setup: We iterate through every cell in the grid. When a building (1) is found, we initialize a queue and perform BFS from that building.
Performing BFS: For each building, we initialize a BFS queue with the building's location, a set vis to keep track of the visited cells, and a variable d set at 0 representing the distance.
- For every level (distance from the building) in the BFS, we increment d by 1.
- We explore the adjacent cells (up, down, right, left) from the current cell in the queue.
- If we encounter an empty land (0) that has not been visited yet, we update the dist and cnt grids for that land space to account for this building's distance and the fact that another building has reached it.
- We also add the empty land to the queue and vis set for further BFS exploration on the next levels.
Tracking Reachable Empty Lands: After BFS completes for all buildings, we must determine if there's an empty land reachable from all buildings. We loop through every cell again, and for each empty land (0), check if the count of buildings (cnt[i][j]) that can reach it is equal to the total number of buildings. Only such lands are potential candidates for the house.
Computing the Optimal Location: Among the possible candidates, we choose the one with the minimum total travel distance (dist[i][j]), and if there's no such location, we return -1.

One thing worth pointing out is the use of the infinite (inf) value to initialize the answer. This allows us to easily update the minimum using the built-in min function as we encounter new potential spots while ensuring that if none are found, we easily recognize this and return -1.

Overall, the solution takes advantage of the properties of BFS to calculate distances level by level which ensures that the shortest path to each empty land is found. By doing so from every building and accumulating the results, we reach a comprehensive solution that evaluates all possible house locations effectively.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider a 3x3 grid:

10 1 0
20 2 0
30 0 0

In this grid:

0s represent empty lands.
1 represents a building.
2 represents an obstacle.

We want to find the position of an empty land (0) to build a new house such that the total Manhattan Distance to all buildings is minimized.

Following the solution approach:

Grid Initialization: First, we initialize our cnt grid to track the number of buildings that can reach each empty land and our dist grid to keep the accumulative distance from all buildings.

1cnt grid:      dist grid:
20 0 0          0 0 0
30 0 0          0 0 0
40 0 0          0 0 0

BFS Setup: We scan the grid cell by cell. When we find the building (at grid[0][1] in this example), we enqueue its position for BFS.
Performing BFS:
- We start the BFS from the building location (0, 1) and initialize our distance d as 0. Our BFS queue initially contains just the building position.
- For each cell in the queue (the BFS level), we increment d by 1 before enqueueing all reachable adjacent land cells (those marked with 0).
- As we perform BFS, when we encounter an empty land, we update the dist and cnt grids. For example, we can move from the building to its left and right to the empty plots at (0, 0) and (0, 2), with each having a distance of 1.

1After first step of BFS:
2cnt grid:      dist grid:
31 0 1          1 0 1
40 0 0          0 0 0
50 0 0          0 0 0

Tracking Reachable Empty Lands: We have completed the BFS for our only building. Now, for every empty land (0), we check if the count (cnt[i][j]) is equal to the total number of buildings (which is 1 in this example).
Computing the Optimal Location: Now we select the empty land with the minimum total travel distance from the dist grid.

Both (0, 0) and (0, 2) are candidates since they each have a building count (cnt) of 1, which is the total number of buildings. We choose the one with the minimum travel distance from dist grid.

In this example, both have the same distance of 1, so either could be chosen as the optimal location:

1Optimal Location: (0, 0) or (0, 2) with a distance of 1.

Had there been multiple buildings, we would perform BFS from each building, accumulate the distances and counts in the dist and cnt grids, and then follow the same steps to select the optimal location based on the total distances and the requirement that the location must be reached by all buildings.

Solution Implementation

1from collections import deque
2
3class Solution:
4    def shortestDistance(self, grid):
5        # Initialize rows `m` and columns `n` based on the grid dimensions
6        m, n = len(grid), len(grid[0])
7      
8        # A queue for breadth-first search
9        queue = deque()
10      
11        # Total number of buildings
12        total_buildings = 0
13      
14        # Data structures to keep count of how many buildings each empty land can reach
15        reach_count = [[0] * n for _ in range(m)]
16      
17        # Data structures to keep track of total distances from each empty land to all buildings
18        distance_sum = [[0] * n for _ in range(m)]
19      
20        # Loop through each cell in the grid
21        for i in range(m):
22            for j in range(n):
23                # If the cell is a building, perform a BFS from this building
24                if grid[i][j] == 1:
25                    total_buildings += 1
26                    queue.append((i, j))
27                    level_distance = 0
28                    visited = set()
29                    while queue:
30                        # Increase the distance level by 1 for each level of BFS
31                        level_distance += 1
32                      
33                        # Loop through each cell in the current BFS level
34                        for _ in range(len(queue)):
35                            r, c = queue.popleft()
36                            # Explore the four directions around the current cell
37                            for dr, dc in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
38                                x, y = r + dr, c + dc
39                                # If the next cell is valid, not visited, and is an empty land
40                                if 0 <= x < m and 0 <= y < n and grid[x][y] == 0 and (x, y) not visited:
41                                    # Increment the building reach count and add the distance
42                                    reach_count[x][y] += 1
43                                    distance_sum[x][y] += level_distance
44                                  
45                                    # Add the cell to the queue and mark it as visited
46                                    queue.append((x, y))
47                                    visited.add((x, y))
48      
49        # Set an initial answer as infinity to find the minimum
50        answer = float('inf')
51      
52        # Loop to find the minimum distance of an empty land cell that can reach all buildings
53        for i in range(m):
54            for j in range(n):
55                if grid[i][j] == 0 and reach_count[i][j] == total_buildings:
56                    answer = min(answer, distance_sum[i][j])
57      
58        # If no cell can reach all buildings, return -1; otherwise, return the minimum distance
59        return -1 if answer == float('inf') else answer
60

1class Solution {
2    public int shortestDistance(int[][] grid) {
3        int rows = grid.length; // Total number of rows in the grid
4        int cols = grid[0].length; // Total number of columns in the grid
5        Deque<int[]> queue = new LinkedList<>(); // Queue to perform BFS
6        int buildings = 0; // Count of buildings in the grid
7        int[][] count = new int[rows][cols]; // Count of buildings each cell can reach
8        int[][] distance = new int[rows][cols]; // Distance from each cell to all buildings
9        int[] directions = {-1, 0, 1, 0, -1}; // Used to explore 4 directions (up, right, down, left)
10
11        // Explore the grid cell by cell
12        for (int i = 0; i < rows; ++i) {
13            for (int j = 0; j < cols; ++j) {
14                // If we find a building, start BFS from here
15                if (grid[i][j] == 1) {
16                    buildings++;
17                    queue.offer(new int[] {i, j});
18                    int depth = 0; // Depth of the BFS, represents the distance from the start
19                    boolean[][] visited = new boolean[rows][cols]; // Visited cells to avoid revisiting
20                    while (!queue.isEmpty()) {
21                        depth++;
22                        for (int k = queue.size(); k > 0; --k) {
23                            int[] point = queue.poll();
24                            for (int l = 0; l < 4; ++l) {
25                                int x = point[0] + directions[l];
26                                int y = point[1] + directions[l + 1];
27                                // Explore the next cell if it's within the grid bounds, is an empty cell, 
28                                // and hasn't been visited from this building
29                                if (x >= 0 && x < rows && y >= 0 && y < cols && 
30                                    grid[x][y] == 0 && !visited[x][y]) {
31                                    count[x][y]++; // Increment reachable buildings count
32                                    distance[x][y] += depth; // Accumulate distance
33                                    queue.offer(new int[] {x, y}); // Add to queue for further exploration
34                                    visited[x][y] = true; // Mark as visited
35                                }
36                            }
37                        }
38                    }
39                }
40            }
41        }
42
43        int minDistance = Integer.MAX_VALUE; // Initialize minimum distance to maximum possible value
44        // Look for the cell that can reach all buildings with the minimum distance
45        for (int i = 0; i < rows; ++i) {
46            for (int j = 0; j < cols; ++j) {
47                // If it's an empty cell and can reach all buildings, it's a potential answer
48                if (grid[i][j] == 0 && count[i][j] == buildings) {
49                    minDistance = Math.min(minDistance, distance[i][j]);
50                }
51            }
52        }
53
54        // If no such cell is found, return -1, otherwise return the minimum distance found
55        return minDistance == Integer.MAX_VALUE ? -1 : minDistance;
56    }
57}
58

1#include <vector>
2#include <queue>
3#include <climits> // For INT_MAX
4
5using namespace std;
6
7class Solution {
8public:
9    int shortestDistance(vector<vector<int>>& grid) {
10        int rows = grid.size();
11        int cols = grid[0].size();
12        vector<vector<int>> count(rows, vector<int>(cols));
13        vector<vector<int>> distanceSum(rows, vector<int>(cols));
14        vector<int> directions = {-1, 0, 1, 0, -1};  // For traversing up, right, down, and left
15        int buildingTotal = 0;  // Number of buildings in the grid
16        int minDistance = INT_MAX;  // Initialize minimum distance with the maximum value
17        queue<pair<int, int>> queue;
18
19        // Iterate over each cell of the grid
20        for (int i = 0; i < rows; ++i) {
21            for (int j = 0; j < cols; ++j) {
22                // Start a BFS traversal from each building
23                if (grid[i][j] == 1) {
24                    buildingTotal++;
25                    queue.emplace(i, j);
26                    vector<vector<bool>> visited(rows, vector<bool>(cols));
27                    int depth = 0;  // The distance from the current building
28
29                    // BFS to traverse the entire grid from the current building
30                    while (!queue.empty()) {
31                        depth++;
32                        for (int size = queue.size(); size > 0; --size) {
33                            auto point = queue.front();
34                            queue.pop();
35                            // Go through all 4 directions
36                            for (int k = 0; k < 4; ++k) {
37                                int x = point.first + directions[k];
38                                int y = point.second + directions[k + 1];
39                                // Check if the new position is within bounds, is empty land, and has not been visited
40                                if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == 0 && !visited[x][y]) {
41                                    visited[x][y] = true;  // Mark the position as visited
42                                    count[x][y]++;  // Increase the count of how many buildings can reach this position
43                                    distanceSum[x][y] += depth;  // Add the distance from the current building
44                                    queue.emplace(x, y);  // Add to the queue for further BFS
45                                }
46                            }
47                        }
48                    }
49                }
50            }
51        }
52
53        // Find the minimum distance sum to all buildings
54        for (int i = 0; i < rows; ++i) {
55            for (int j = 0; j < cols; ++j) {
56                // Check if it's possible to reach all buildings from this cell
57                if (grid[i][j] == 0 && count[i][j] == buildingTotal) {
58                    minDistance = min(minDistance, distanceSum[i][j]);
59                }
60            }
61        }
62
63        return minDistance == INT_MAX ? -1 : minDistance;  // If no such empty land exists, return -1
64    }
65};
66

1const directions: number[] = [-1, 0, 1, 0, -1]; // Used to move up, right, down, and left
2
3function shortestDistance(grid: number[][]): number {
4    const rows = grid.length;
5    const cols = grid[0].length;
6    const count: number[][] = Array.from({ length: rows }, () => new Array(cols).fill(0));
7    const distanceSum: number[][] = Array.from({ length: rows }, () => new Array(cols).fill(0));
8    let buildingTotal: number = 0;  // Number of buildings in the grid
9    let minDistance: number = Number.MAX_SAFE_INTEGER;  // Initialize minimum distance with a safe large number
10
11    for (let i = 0; i < rows; ++i) {
12        for (let j = 0; j < cols; ++j) {
13            // Perform a BFS traversal from each building
14            if (grid[i][j] === 1) {
15                buildingTotal++;
16                const queue: [number, number][] = [];
17                queue.push([i, j]);
18                let depth: number = 0;  // The distance from the current building
19                const visited: boolean[][] = Array.from({ length: rows }, () => new Array(cols).fill(false));
20
21                // BFS to traverse the grid from the current building
22                while (queue.length > 0) {
23                    const levelSize: number = queue.length;
24                    depth++;
25                    for (let q = 0; q < levelSize; ++q) {
26                        const point = queue.shift()!;
27                        // Iterate through 4 directions
28                        for (let k = 0; k < 4; ++k) {
29                            const x = point[0] + directions[k];
30                            const y = point[1] + directions[k + 1];
31                            // Check if the position is within bounds, is empty land and hasn't been visited
32                            if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] === 0 && !visited[x][y]) {
33                                visited[x][y] = true;
34                                count[x][y]++;
35                                distanceSum[x][y] += depth;
36                                queue.push([x, y]);
37                            }
38                        }
39                    }
40                }
41            }
42        }
43    }
44
45    // Find the minimum distance to all buildings
46    for (let i = 0; i < rows; ++i) {
47        for (let j = 0; j < cols; ++j) {
48            if (grid[i][j] === 0 && count[i][j] === buildingTotal) {
49                minDistance = Math.min(minDistance, distanceSum[i][j]);
50            }
51        }
52    }
53
54    // Return minimum distance or -1 if no such empty land exists that can reach all buildings
55    return minDistance === Number.MAX_SAFE_INTEGER ? -1 : minDistance;
56}
57

Not Sure What to Study? Take the 2-min Quiz：

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function callDetermine return valueDetermine how many recursive calls will be madeTracing the recursive calls

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O((m * n) * (m * n)), where m is the number of rows and n is the number of columns in the grid.

Here's the breakdown of the complexity:

The nested loop to iterate through the grid takes O(m * n).
The BFS algorithm runs in O(m * n) for each building found. Since it runs once for each building, and there could be up to m * n buildings in the worst case, the total complexity for BFS across all buildings would be O((m * n) * (m * n)).

Space Complexity

The space complexity of the code is O(m * n) due to the following reasons:

The cnt and dist grids each take O(m * n) space.
The vis set and queue q can each take up to O(m * n) space in the worst case when all cells are queued or visited.
Constant factors such as the directions array and the integer total do not significantly affect the space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

TrueFalse

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

317. Shortest Distance from All Buildings

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings