317.Shortest_Distance_from_All_Buildings(Hard).md

317. Shortest Distance from All Buildings (Hard)

Date and Time: May 9, 2025

Link: https://leetcode.com/problems/shortest-distance-from-all-buildings

Walk-through:

We can run BFS on each building 1 to all empty land 0, and we use a hashmap to save each 0's position with its [steps, buildings], where we use steps to keep track of the total steps that each building 1 to reach there and buildings to record how many buildings will pass this empty island.

Finally, loop over hashmap and check if 0's building has met the requirement and we update ans with the minimum steps.

Python:

class Solution:
    def shortestDistance(self, grid: List[List[int]]) -> int:
        # Q: Return the shortest distance from a grid to all buildings
        # S: run BFS from 1 to all 0, create a new hashmap {(r, c): [steps, buildings]} to store each grid's [steps, buildings], if we run bfs from 1, increment each 0's buildings
        # Loop over hashmap to check if buildings is met, update steps with the minimum
        # TC: O(m^2 * n^2), SC: O(m*n)

        rows, cols = len(grid), len(grid[0])
        hashmap = {}    # {pos of 0: [steps, buildings]}
        # Loop over grid to find 1 and run BFS
        directions = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        def bfs(r, c):
            deque = collections.deque([(r, c, 0)])
            visited = set()
            visited.add((r, c))
            while deque:
                r, c, steps = deque.popleft()
                for dr, dc in directions:
                    row, col = r+dr, c+dc
                    if (row, col) not in visited and row in range(rows) and col in range(cols) and grid[row][col] == 0:
                        # Add steps to (row, col) and increment buildings by 1
                        # Intialize hashmap
                        hashmap[(row, col)] = hashmap.get((row, col), [0, 0])
                        hashmap[(row, col)][0] += steps + 1
                        hashmap[(row, col)][1] += 1
                        visited.add((row, col))
                        deque.append([row, col, steps+1])
        # Call BFS on each 1
        ones = 0
        ans = float("inf")
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    ones += 1
                    bfs(r, c)
        # Loop over hashmap to find the minimum steps
        for _, vals in hashmap.items():
            steps, buildings = vals
            if buildings == ones:
                ans = min(ans, steps)
        return ans if ans != float("inf") else -1

Time Complexity: $O(m^2 * n^2)$
Space Complexity: $O(m*n)$