Firstly, the manhattan distance should be calculated for x coordinate and y coordinate separately. Combine the result of x and y, you will get the final result.

After turning into one dimensional problem. There still one assumption that the optimized point must fall on one of these points. This needs a little bit math and imagination.

Then when we traverse the coordinate array, we first sort the array. Then, if there is any duplicate element, we do not need calculate twice. The distance is calculate by the prev + i * diff - (len - i) * diff

Here, i * diff means the first half, (len - i) means the second half.

```
public int minTotalDistance(int[][] grid) {
int m = grid.length;
if (m <= 0) {
return 0;
}
int n = grid[0].length;
if (n <= 0) {
return 0;
}
int[] xCord = new int[n * m];
int xLen = 0;
int[] yCord = new int[n * m];
int yLen = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] >= 1) {
xCord[xLen++] = i;
yCord[yLen++] = j;
}
}
}
return findDist(xCord, xLen) + findDist(yCord, yLen);
}
// There are one assumptions that hold here.
// The best point must be one of the point on the line.
public int findDist(int[] nums, int len) {
Arrays.sort(nums, 0, len);
int prevNum = nums[0];
int prev = 0;
// Calculate the dist for first number.
for (int i = 1; i < len; i++) {
prev += nums[i] - prevNum;
}
for (int i = 1; i < len; i++) {
int curr = 0;
int num = nums[i];
if (prevNum == num) {
continue;
}
// The dist from current to previous.
int diff = num - prevNum;
curr = prev + i * diff - (len - i) * diff;
if (curr > prev) {
return prev;
}
prev = curr;
prevNum = num;
}
return prev;
}
```