LeetCode 317: Shortest Distance from All Buildings
LeetCode 317 Solution Explanation
Explanation:
This problem can be solved using a breadth-first search (BFS) approach. We will perform BFS starting from each building to calculate the shortest distance to all buildings for each empty land. We will maintain two matrices - one to store the total distance to all buildings from each empty land, and the other to store the number of buildings each empty land is reachable from.
- Initialize a grid to represent the city with buildings, empty lands, and obstacles.
- Initialize two matrices of the same size as the grid to store the total distance and the number of buildings reachable from each empty land.
- For each building, perform BFS to calculate the distance to all empty lands reachable from that building.
- Update the total distance matrix and the reachable buildings matrix accordingly.
- Finally, find the empty land with the minimum total distance and reachable from all buildings.
Time Complexity: Let's denote n as the number of rows, m as the number of columns, and b as the number of buildings. The time complexity is O(nmb) as we perform BFS from each building.
Space Complexity: O(n*m) for the two matrices to store total distance and reachable buildings.
:
LeetCode 317 Solutions in Java, C++, Python
public int shortestDistance(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int[][] totalDistance = new int[rows][cols];
int[][] reachableBuildings = new int[rows][cols];
int totalBuildings = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 1) {
totalBuildings++;
bfs(grid, i, j, totalDistance, reachableBuildings);
}
}
}
int minDistance = Integer.MAX_VALUE;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 0 && reachableBuildings[i][j] == totalBuildings) {
minDistance = Math.min(minDistance, totalDistance[i][j]);
}
}
}
return minDistance == Integer.MAX_VALUE ? -1 : minDistance;
}
private void bfs(int[][] grid, int row, int col, int[][] totalDistance, int[][] reachableBuildings) {
int rows = grid.length;
int cols = grid[0].length;
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{row, col});
boolean[][] visited = new boolean[rows][cols];
int distance = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] curr = queue.poll();
for (int[] dir : directions) {
int nextRow = curr[0] + dir[0];
int nextCol = curr[1] + dir[1];
if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols
&& grid[nextRow][nextCol] == 0 && !visited[nextRow][nextCol]) {
totalDistance[nextRow][nextCol] += distance;
reachableBuildings[nextRow][nextCol]++;
visited[nextRow][nextCol] = true;
queue.offer(new int[]{nextRow, nextCol});
}
}
}
distance++;
}
}Interactive Code Editor for LeetCode 317
Improve Your LeetCode 317 Solution
Use the editor below to refine the provided solution for LeetCode 317. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...