LeetCode 317: Shortest Distance from All Buildings Solution

Master LeetCode problem 317 (Shortest Distance from All Buildings), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

317. Shortest Distance from All Buildings

Hard

Array Breadth-First Search Matrix

Problem 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.

Solution Code

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++;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 317 (Shortest Distance from All Buildings)?

This page provides optimized solutions for LeetCode problem 317 (Shortest Distance from All Buildings) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 317 (Shortest Distance from All Buildings)?

The time complexity for LeetCode 317 (Shortest Distance from All Buildings) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 317 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 317 in Java, C++, or Python.

Back to LeetCode Solutions