> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/math/296.-best-meeting-point.md).

# 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](http://en.wikipedia.org/wiki/Taxicab_geometry), 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.
```

```cpp
int minTotalDistance(vector<vector<int>>& grid) { // time: O(m * n); space: O(m * n)
    vector<int> rows, cols;
    for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j < grid[0].size(); ++j) {
            if (grid[i][j] == 1) {
                rows.push_back(i);
                cols.push_back(j);
            }
        }
    }
    // No need to sort rows since it is already sorted based on the way we loop
    sort(cols.begin(), cols.end());
    int res = 0, i = 0, j = rows.size() - 1;
    while (i < j) {
        res += (rows[j] - rows[i]) + (cols[j--] - cols[i++]);
    }
    return res;
}
```