LeetCode-Best Meeting Point

296. Best Meeting Point

Total Accepted: 6496
Total Submissions: 13313
Difficulty: Hard

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

For example, given three people living at (0,0), (0,4), and (2,2):

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

Analysis:

https://discuss.leetcode.com/topic/51109/8ms-c-dp-solution-with-o-mn-time-o-m-n-space

Solution:

 1 public class Solution {
 2     public int minTotalDistance(int[][] grid) {
 3         if (grid.length==0 || grid[0].length==0) return 0;
 4         
 5         int rows = grid.length, cols = grid[0].length;
 6         int[] xNums = new int[cols];
 7         int[] yNums = new int[rows];
 8         int initDis = 0; // Distance to (0,0)
 9 
10         for (int i=0;i<rows;i++){
11             int sum = 0;
12             for (int j=0;j<cols;j++){
13                 sum += grid[i][j];
14                 xNums[j] +=sum;
15                 // Update init distance
16                 if (grid[i][j] == 1){
17                     initDis += (i+j);
18                 }
19             }
20             yNums[i] = xNums[cols-1];
21         }
22 
23         int totalNum = xNums[cols-1];
24         // find out the optimal point on xNums.
25         int minDis = initDis;
26         for (int i=1;i<cols;i++){
27             int curDis = minDis + xNums[i-1] - (totalNum - xNums[i-1]);
28             if (curDis < minDis){
29                 minDis = curDis;
30             } else break;
31         }
32 
33         // find out the optimal point on yNums.
34         for (int i=1;i<rows;i++){
35             int curDis = minDis + yNums[i-1] - (totalNum -yNums[i-1]);
36             if (curDis < minDis) {
37                 minDis = curDis;
38             } else break;
39         }
40         return minDis; 
41     }
42 }