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 - 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.

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;
    }
};