Leetcode 296 Best Meeting Point

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.

Solution 1: best meeting point of one-dimension is at the middle point. for 2D is the same. find the mid-x and mid-y, it is the meeting place.

 public class Solution {  
   public int minTotalDistance(int[][] grid) {  
     int m=grid.length;  
     if (m==0) return 0;  
     int n=grid[0].length;  
     int[] row=new int[n];  
     int[] col=new int[m];  
     for (int i=0;i<m;i++) {  
       for (int j=0; j<n;j++) {  
         if (grid[i][j]==1) {  
           col[i]++;  
           row[j]++;  
         }  
       }  
     }  
     int res=0;  
     int i=0, j=n-1;  
     while (i<j) {  
       int min=Math.min(row[i],row[j]);  
       res+=min*(j-i);  
       if ((row[i]-=min)==0) i++;  
       if ((row[j]-=min)==0) j--;  
     }  
     i=0; j=m-1;  
     while (i<j) {  
       int min=Math.min(col[i],col[j]);  
       res+=min*(j-i);  
       if ((col[i]-=min)==0) i++;  
       if ((col[j]-=min)==0) j--;  
     }  
     return res;  
   }  
 }