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 *B*1 and *B*2 then *dist*[*i*][*j*] = *dist*_{B1}_{ij} + *dist*_{B2}_{ij})

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*((*n*^{2})(*m*^{2}))

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

EDIT: I hand't understood the problem statement correctly. Sorry!

but if you only consider a empty cell only one time (the closest building to this cell will mark it as visited) then how do you know the sum of the distances to this cell from the rest of the buildings?

Thanks for you help!

EDIT:Oh, I did not see your update.Edit:Sorry, I hadn't seen the walls.You might want to start n(B) simultaneous BFS'es from each B, keep track of cells visited by each of them, and for each reachable cell keep the sum of BFS'es which hit it already. Once a cell with n(hits)=n(B) is found you break the search. Time complexity would be n(B) * max_distance_from_best_cell_to_furthest_B; still O(N*N) = O(n*n*m*m) (same as establishing distance between each two cells in the grid), but you break earlier.

I got it! Thanks.