[LeetCode] Shortest Distance from All Buildings

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

  • Each 0 marks an empty land which you can pass by freely.
  • Each 1 marks a building which you cannot pass through.
  • Each 2 marks an obstacle which you cannot pass through.

For example, given three buildings at (0,0)(0,4)(2,2), and an obstacle at (0,2):

The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.

Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

Java solution:

 

Time complexity:

The time complexity for BFS/DFS is O(|V|+|E|),  In this problem, every vertex has up to 4 edges (left, right, up, down), so |E| ~ 4|V|. Thus, you have overall O(|V|) = O(mn) for a BFS. This has been proven for all sparse graphs like this problem. Now, we do a BFS for each building, so the overall complexity is O(#buildings*(mn)). In worst case, every vertex is a building. So the number of buildings is also upper bounded by O(mn), and thus you have O((mn)(mn)) = O(m^2n^2). This is a very loose bound since when every vertex is a building, we don’t even need to do a BFS (nowhere to go).

https://discuss.leetcode.com/topic/31925/java-solution-with-explanation-and-time-complexity-analysis/5