317. Shortest Distance from All Buildings

leetcode_317.md

Description

You are given an m x n grid grid of values 0, 1, or 2, where:

• each 0 marks an empty land that you can pass by freely,
• each 1 marks a building that you cannot pass through, and
• each 2 marks an obstacle that you cannot pass through. You want to build a house on an empty land that reaches all buildings in the shortest total travel distance. You can only move up, down, left, and right.

Return the shortest travel distance for such a house. If it is not possible to build such a house according to the above rules, return -1.

The total travel distance is the sum of the distances between the houses of the friends and the meeting point.

The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Link to the original problem

Example 1:

Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7
Explanation: 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.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] is either 0, 1, or 2.
• There will be at least one building in the grid.

Idea

1. This question is another epic one of the "shortest path in a grid" series, also it's asked a lot in recent FANNG interview according to Leetcode.
2. OK, so how is this problem different than the other questions in the series?
3. We saw obstacles in the series multiple times already, so that's not scary. However, this time we need to find the shortest path to all the buildings.
4. Hmm, ok, that's a little bit scary.
5. Let's calm down again, as always, and find out what we can do.
6. So we still have our old friend BFS. Suppose we found our ideal cell in the grid to build the house, that has shortest travel distance to all buildings, we can definitely use BFS to find the distances to all the buildings.
7. So we can brute force all the cells to try to find all the shorest paths and sum them and find the minimum one.
8. And the time complexity of it is O(m^2 * n^2), because we need to traverse the whole grid (which is O(m*n) from the BFS) every time we start from a cell in the grid (which has O(m*n) cells).
9. One thing we need to remember is that how many building can we reach from the current cell, and we need to reach all the buildings to make it a valid candidate cell.
10. So for that purpose we need to allocate an array reach of dimension (m,n) to tell how many buildings we can reach from each cell.
11. Is it the end now? Actually no.
12. Because some of the readers might ask, can we do better than that?
13. Actually it depends, it depends on if we have more empty cells to build the house or buildings.
14. According to the question description, we cannot say 100% sure that we have always more empty cells than buildings. So let's find out.
15. Because the path "from house to building" is the same as "from building to house".
16. So we can start BFS from the building to reach all the houses, and at last we can compare the distances and reaches and found out the minimum one. So the worst case time complexity is still O(m^2 * n^2).
17. After some testing, I see that for the test cases we seem to have more empty cells than buidling, because the running time of "from house to building" is around 7 times of "from building to house".
18. If you are doing an interview and you shares this finding, I believe the interviewer is gonna be impressed. LOL!
19. Below I shared two versions of the solution, which are quite similar, and they should be self-explanatory enough.
20. Let me know if you have any question, I'm more than happy to discuss about it.
21. Thanks for your time!

Solution

Javascript 1

// From house to building
const shortestDistance = function(grid) {
  const R = grid.length, C = grid[0].length;
  const distances = Array(R).fill(0).map(_ => Array(C).fill(0));
  const reach = Array(R).fill(0).map(_ => Array(C).fill(0));
  const isValid = (x, y) => x >= 0 && x < R && y >= 0 && y < C;
  const genKey = (x, y) => x * C + y;

  // find empty cells and start bfs from that point.
  let buildingCount = 0;
  for (let i = 0; i < R; i += 1) {
    for (let j = 0; j < C; j += 1) {
      if (grid[i][j] == 1) {
        buildingCount += 1;
      } else if (grid[i][j] == 0) {
        bfs(i, j);
      }
    }
  }
  // find minimum distance if that point reaches to all buildings
  let ans = Infinity;
  for (let i = 0; i < R; i += 1) {
    for (let j = 0; j < C; j += 1) {
      if (grid[i][j] == 0 && reach[i][j] == buildingCount) {
        ans = Math.min(distances[i][j], ans);
      }
    }
  }
  return ans == Infinity ? -1 : ans;

  function bfs(i,j) {
    const queue = [[i, j, 0]]; // [indexI, indexJ, distance]
    const visited = new Set();
    while (queue.length) {
      const [r, c, dist] = queue.shift();
      [[r+1,c], [r,c-1], [r-1,c], [r,c+1]].forEach(([x, y]) => {
        const key = genKey(x, y);
        if (isValid(x, y) && !visited.has(key)) {
          visited.add(key);
          if (grid[x][y] == 0) {
            queue.push([x, y, dist + 1]);
          } else if (grid[x][y] == 1) {
            distances[i][j] += dist + 1;
            reach[i][j] += 1;
          }
        }
      });
    }
  }
};

Javascript 2

// From building to house
const shortestDistance = function(grid) {
  const R = grid.length, C = grid[0].length;
  const distances = Array(R).fill(0).map(_ => Array(C).fill(0));
  const reach = Array(R).fill(0).map(_ => Array(C).fill(0));
  const isValid = (x, y) => x >= 0 && x < R && y >= 0 && y < C;
  const genKey = (x, y) => x * C + y;

  // find building and start bfs from that point.
  let buildingCount = 0;
  for (let i = 0; i < R; i += 1) {
    for (let j = 0; j < C; j += 1) {
      if (grid[i][j] == 1) {
        buildingCount += 1;
        bfs(i, j);
      }
    }
  }
  // find minimum distance if that point reaches to all buildings
  let ans = Infinity;
  for (let i = 0; i < R; i += 1) {
    for (let j = 0; j < C; j += 1) {
      if (grid[i][j] == 0 && reach[i][j] == buildingCount) {
        ans = Math.min(distances[i][j], ans);
      }
    }
  }
  return ans == Infinity ? -1 : ans;

  function bfs(i,j) {
    const queue = [[i, j, 0]]; // [indexI, indexJ, distance]
    const visited = new Set();
    while (queue.length) {
      const [r, c, dist] = queue.shift();
      [[r+1,c], [r,c-1], [r-1,c], [r,c+1]].forEach(([x, y]) => {
        const key = genKey(x, y);
        if (isValid(x, y) && !visited.has(key) && grid[x][y] == 0) {
          queue.push([x, y, dist + 1]);
          distances[x][y] += dist + 1;
          reach[x][y] += 1;
          visited.add(key);
        }
      });
    }
  }
};

References

1. Leetcode 1730
2. Leetcode 1091
3. Leetcode 1293
4. Leetcode 864