Question

Formatted question description: https://leetcode.ca/all/296.html

 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.

Hint:
Try to solve it in one dimension first. How can this solution apply to the two dimension case?



Algorithm

First look at the situation where there are two points A and B in one dimension.

______A_____P_______B_______


It can be found that as long as the meeting is that the location P is in the interval [A, B], no matter where it is, the sum of the distances is the distance between A and B. If P is not between [A, B], then the sum of the distances is Will be greater than the distance between A and B, now add two more points C and D:

______C_____A_____P_______B______D______


The best position of point P is in the interval [A, B], so that the sum of the distances from the four points is the AB distance plus the CD distance.

Just sort the positions, then subtract the first coordinate from the last coordinate, which is the CD distance, and subtract the second coordinate from the penultimate, the second coordinate, which is the AB distance. And so on, until the middle stop.

The one-dimensional situation is analyzed, and the two-dimensional situation is the addition of two one-dimensional results.

Code

Java

• import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Best_Meeting_Point {

public static void main(String[] args) {
Best_Meeting_Point out = new Best_Meeting_Point();
Solution s = out.new Solution();

System.out.println(s.minTotalDistance(new int[][] { {1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0} }));
}

public class Solution {
public int minTotalDistance(int[][] grid) {

// empty, null check

List<Integer> ipos = new ArrayList<>();
List<Integer> jpos = new ArrayList<>();

for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
}
}
}

int sum = 0;

// ipos already sorted, since above it's iterating over grid via i index
int iMid = ipos.get(ipos.size() / 2);
for(Integer pos : ipos){
sum += Math.abs(pos - iMid);
}

Collections.sort(jpos);
int jMid = jpos.size() / 2;
for (int j = 0; j < jpos.size(); j++) {
sum += Math.abs(jpos.get(jMid) - jpos.get(j));
}

return sum;
}
}
}

• // OJ: https://leetcode.com/problems/best-meeting-point/
// Time: O(MN^2)
// Space: O(MN)
class Solution {
public:
int minTotalDistance(vector<vector<int>>& A) {
int M = A.size(), N = A[0].size(), ans = INT_MAX, dist[201][201] = {}, up[201][201] = {}, down[201][201] = {}, cnt[201] = {};
for (int i = 0; i < M; ++i) {
int sum = 0, left = 0, right = 0;
for (int j = 0; j < N; ++j) {
if (A[i][j] == 0) continue;
sum += j;
right++;
}
for (int j = 0; j < N; ++j) {
dist[i][j] = sum;
if (A[i][j]) ++left, --right;
sum += left - right;
}
cnt[i] = left;
}
int c = cnt[0];
for (int i = 1; i < M; ++i) {
for (int j = 0; j < N; ++j) {
int mn = INT_MAX;
for (int k = 0; k < N; ++k) {
mn = min(mn, dist[i - 1][k] + (abs(j - k) + 1) * c);
}
up[i][j] = up[i - 1][j] + mn;
}
c += cnt[i];
}
c = cnt[M - 1];
for (int i = M - 2; i >= 0; --i) {
for (int j = 0; j < N; ++j) {
int mn = INT_MAX;
for (int k = 0; k < N; ++k) {
mn = min(mn, dist[i + 1][k] + (abs(j - k) + 1) * c);
}
down[i][j] = down[i + 1][j] + mn;
}
c += cnt[i];
}
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
ans = min(ans, dist[i][j] + up[i][j] + down[i][j]);
}
}
return ans;
}
};

• class Solution(object):
def minTotalDistance(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
iList, jList, ppl = [], [], []
for i in range(0, len(grid)):
for j in range(0, len(grid[0])):
if grid[i][j] == 1:
ppl.append((i, j))
iList.append(i)
jList.append(j)
jList.sort()
m = (iList[len(iList) / 2], jList[len(jList) / 2])
return sum(map(lambda p: abs(p[1] - m[1]) + abs(p[0] - m[0]), ppl))