Best Meeting Point

A group of 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 - 0The point

`(0,2)`

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

Dynamic programming.

Brute force solution is trivial. O(n^4).

This solution optimize it to O(n^2)

Decompose the 2D manhattan distance into two 1D manhattan distance, since the two dimension is individual.

class Solution { public: int INTMAX = 0x7fffffff; int minTotalDistance(vector<vector<int>>& grid) { if(grid.size() == 0 || grid[0].size() == 0) return 0; int rows = grid.size(); int columns = grid[0].size(); int distance; int countC[columns]; // number of 1s in each column int countR[rows]; // number of 1s in each row int sumRestR[rows]; // sumRestR[i] = all the int sumRestC[columns]; for(int r = 0; r < rows; r++){ countR[r] = 0; for(int c = 0; c < columns; c++){ if(grid[r][c] == 1) countR[r]++; } } for(int c = 0; c < columns; c++){ countC[c] = 0; for(int r = 0; r < rows; r++){ if(grid[r][c] == 1) countC[c]++; } } for(int i = 0; i < rows; i++){ sumRestR[i] = 0; for(int j = 0; j < rows; j++){ sumRestR[i] += abs(j - i) * countR[j]; } } for(int i = 0; i < columns; i++){ sumRestC[i] = 0; for(int j = 0; j < columns; j++){ sumRestC[i] += abs(j - i) * countC[j]; } } distance = INTMAX; for(int r = 0; r < rows; r++){ for(int c = 0; c < columns; c++){ distance = min(distance, sumRestR[r] + sumRestC[c]); } } return distance; } };