# 8ms C++ DP solution with O(mn) time & O(m + n) space

• 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;
}
};
``````

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