My solution to the 1-D version of this problem is to calculate the distance sum to Position `0`

first, then move the Position from `0`

to `1`

, update the distance sum, and repeat to find the minimum distance sum.

Moving Position from `i`

to `i + 1`

, the distance sum will be incremented by the number of the people in `[0, i]`

and also decremented by the number of the people in `[i + 1, n - 1]`

.

Thus, the DP transition equation is `dist[i] = dist[i - 1] + #[0, i] - #[i + 1, n - 1]`

, where `dist[i]`

denotes the sum of the distances between each person's position and Position `i`

, and `#[i, j]`

denotes the number of people within position window `[i, j]`

.

It is obvious that we can stop moving once the number of people in `[0, i]`

is no less than the number in `[i + 1, n - 1]`

, i.e., `#[0, i] - #[i + 1, n - 1] >= 0`

, which means we have reached the median.

In order to count the number of people within a position range, we can use range sum (https://leetcode.com/problems/range-sum-query-immutable/) to deal with it.

To solve the 2-D version of the problem, we can use a similar way.

We first find the accumulated sums of the numbers of people `y_count`

& `x_count`

vertically and horizontally, respectively, and the distance sums `y_dist`

& `x_dist`

which represent the sum of the distance between each person's position to Row `0`

and Column `0`

, respectively.

Similarly, we find the minimum distance sum horizontally and vertically, and the answer will be the sum of both minimum distance.

For example, the grid is

```
1 0 0 0 1
0 0 0 0 0
0 0 1 0 0
```

So the `x_count`

will be `[1, 1, 2, 2, 3]`

, `y_count`

will be `[2, 2, 3]`

, and the initial `x_dist`

will be `0 + 4 + 2 = 6`

, the initial `y_dist`

will be `0 + 0 + 2 = 2`

. Thus, the distance sums of each position will be

```
median
median 6+2 5+2 4+2 | 5+2 6+2
--------------------------
6+3 5+3 4+3 5+3 6+3
6+4 5+4 4+4 5+4 6+4
```

Actually, what we do is to find the minimum separately:

horizontally: `6, 6+1-(3-1)=5, 5+1-(3-1)=4`

`4+2-(3-2)=5, 5+2-(3-2)=6`

vertically: `2`

`2+2-(3-2) = 3, 3+2-(3-2)=4`

Therefore, the result is `4+2=6`

.

```
class Solution {
public:
int minTotalDistance(vector<vector<int>>& grid) {
int m = (int)grid.size(), n = m == 0 ? 0 : (int)grid[0].size();
if (n == 0) return 0;
int y_count[m] = {0}, x_count[n] = {0};
int y_dist = 0, x_dist = 0;
for (int i = 0; i != m; ++i) {
y_count[i] = i == 0 ? 0 : y_count[i - 1];
for (int j = 0; j != n; ++j) {
y_count[i] += grid[i][j];
x_count[j] += y_count[i] - (i == 0 ? 0 : y_count[i - 1]);
x_dist += grid[i][j] * j;
y_dist += grid[i][j] * i;
}
}
int reduced = 0;
for (int i = 0; i != m - 1 && (reduced = y_count[i] - (y_count[m - 1] - y_count[i])) < 0; ++i)
y_dist += reduced;
for (int j = 0; j != n - 1 && (reduced = x_count[j] - (x_count[n - 1] - x_count[j])) < 0; ++j)
x_dist += reduced;
return x_dist + y_dist;
}
};
```