# 6ms C++ quick partition solution without sort

• ``````
class Solution {
public:
int minTotalDistance(vector<vector<int>>& grid) {
// min sum [abs(p2x - p1x) + abs(p2y - p1y)]
// = min sum (abs(p2x - p1x)) + min sum (abs(p2y - p1y)
// geometric median of 1-D line is the median
int m = grid.size();
if (m == 0) return 0;
int n = grid[0].size();
if (n == 0) return 0;
vector<int> xgrid;
vector<int> ygrid;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
xgrid.push_back(i);
ygrid.push_back(j);
}
}
}
nth_element(xgrid.begin(), xgrid.begin() + xgrid.size()/2, xgrid.end());
nth_element(ygrid.begin(), ygrid.begin() + ygrid.size()/2, ygrid.end());
int xmid = xgrid[xgrid.size() / 2];
int ymid = ygrid[ygrid.size() / 2];
int dist = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1)
dist += abs(xmid - i) + abs(ymid - j);
}
}
return dist;
}
};

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.