296. Best Meeting Point

• Difficulty: Hard

• Topics: Math, Sort

• Similar Questions:

  • Shortest Distance from All Buildings

  • Minimum Moves to Equal Array Elements II

Problem:

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

Example:

Input: 

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

Output: 6 

Explanation: Given three people living at (0,0), (0,4), and (2,2):
             The point (0,2) is an ideal meeting point, as the total travel distance 
             of 2+2+2=6 is minimal. So return 6.

Solutions:

class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        int m = grid.size();
        if (m == 0) return 0;
        int n = grid[0].size();
        if (n == 0) return 0;

        vector<int> x, y;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    x.push_back(i);
                    y.push_back(j);
                }
            }
        }

        sort(y.begin(), y.end()); // sorting!!!!!!!

        return minTotalDistanceAtOneDimension(x) + minTotalDistanceAtOneDimension(y);
    }

private:
    int minTotalDistanceAtOneDimension(vector<int>& points) { // it is median!!! not average!!!
        int distance = 0;
        int i = 0;
        int j = points.size() - 1;
        while (i < j) {
            distance += points[j] - points[i];
            i++;
            j--;
        }
        cout << distance << endl;
        return distance;
    }
};