### deinier's blog

By deinier, 7 years ago, 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? bfs, Comments (5)