Hi community!
I was requested to solve this problem few months ago in an onsite interview and I would like to know the best approach to solve it.
Problem statement:
You have a n * m grid with B (building), # (wall) and . (empty) and we want to know the coordinates i,j of a empty cell where the sum of the distances from all the buildings B to this cell is minimized. In each step you can move up, down, left and right. Each empty cell i,j is reachable for each building B.
My approach:
dist[i][j] -> sum of the distances from cell i,j to all buildings. (if we have B1 and B2 then dist[i][j] = distB1ij + distB2ij)
For each cell with a building B, apply BFS and increment dist[i][j] for all positions i, j reachable from B with the min distance from B to i, j in the grid.
Answer: min(dist[i][j]) where grid[i][j] is an empty cell.
Complexity:
O(n * m * (|V| + |E|)) where |V| is vertex amount (n * m) and |E| is edge amount (n * m).
at the end, I think my approach is O((n2)(m2))
My bad: I did not ask for any constraints. (Maybe I was a bit nervous that day)
Do you have another approach to this problem?
Am I wrong with this approach?
Thanks in advance.
Full text and comments »