# 12-13 lines C++

• Treat the two dimensions x and y separately, first collecting the k coordinates of the dimension and then using them to update the total travel distance.

Solution 1 ... `nth_element` ... 12 ms, O(mn) average

Find the median coordinate and sum the distances to the median.

``````int minTotalDistance2(vector<vector<int>>& grid) {
int total = 0, X = grid.size(), Y = grid[0].size();
for (int dim=0; dim<2; ++dim) {
int c[X*Y], k = 0;
for (int x=0; x<X; ++x)
for (int y=0; y<Y; ++y)
if (grid[x][y])
c[k++] = dim ? y : x;
nth_element(c, c+k/2, c+k);
int louis = c[k/2];  // (co)median
while (k--)
total += abs(louis - c[k]);
}
}
``````

Solution 2 ... `sort` ... 12 ms, O(mn log(mn))

Sort the coordinates and use larrywang2014's way to add the travel distances.

``````int minTotalDistance(vector<vector<int>>& grid) {
int total = 0, X = grid.size(), Y = grid[0].size();
for (int dim=0; dim<2; ++dim) {
int i = 0, k = 0, c[X*Y];
for (int x=0; x<X; ++x)
for (int y=0; y<Y; ++y)
if (grid[x][y])
c[k++] = dim ? y : x;
sort(c, c+k);
while (i < --k)
total += c[k] - c[i++];
}