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	1
0	0	0
0	1	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. Median in Math. Collect coordinates in sorted order.

 1 public class Solution {
 2     public int minTotalDistance(int[][] grid) {
 3             int m = grid.length, n = grid[0].length;
 4         int total = 0, Z[] = new int[m*n];
 5         for (int dim=0; dim<2; ++dim) {
 6             int i = 0, j = 0;
 7             if (dim == 0) {
 8                 for (int x=0; x<n; ++x)
 9                     for (int y=0; y<m; ++y)
10                         if (grid[y][x] == 1)
11                             Z[j++] = x;
12             } else {
13                 for (int y=0; y<m; ++y)
14                     for (int g : grid[y])
15                         if (g == 1)
16                             Z[j++] = y;
17             }
18             while (i < --j)
19                 total += Z[j] - Z[i++];
20         }
21         return total;
22     }
23 }

Solution 2. Count how many people live in each row and each column. Only O(m+n) space.

 1 public class Solution {
 2     public int minTotalDistance(int[][] grid) {
 3         int m = grid.length, n = grid[0].length;
 4         int[] I = new int[m], J = new int[n];
 5         for (int i=0; i<m; ++i)
 6             for (int j=0; j<n; ++j)
 7                 if (grid[i][j] == 1) {
 8                     ++I[i];
 9                     ++J[j];
10                 }
11         
12         int total = 0;
13         for (int[] K : new int[][]{ I, J }) {
14             int i = 0, j = K.length - 1;
15             while (i < j) {
16                 int k = Math.min(K[i], K[j]);
17                 total += k * (j - i);
18                 if ((K[i] -= k) == 0) ++i;
19                 if ((K[j] -= k) == 0) --j;
20             }
21         }
22         return total;
23     }
24 }