C++ 6ms DP, O(mn) time, O(m+n) space with explanations

• If the meet distance at point `(i, j)` is `X`, people from `col[0]` to `col[j]` is `a`, people from `col[j+1]` to `col[n-1]` is `b`, the meet distance at point `(i, j+1)` is `X + a - b`. Because `b = total - a`, `X + a - b` => `X + 2a - total`

Same rule applied to rows.

So, use two vectors `vector<int> row` and `vector<int> col` . `row[i]` and `col[j]` store the accumulative number of people to row `i` and column `j` respectively.

In the meantime of calculating the accumulative values, get the meet distance `base` at point `(0, 0)` and `total` people

Finally, traverse all points and calculate the meet distance at each point and find the minimum distance.

``````    int minTotalDistance(vector<vector<int>>& grid) {
int m = grid.size();
if (m == 0) return 0;
int n = grid[0].size();
vector<int> row(m, 0);
vector<int> col(n, 0);
int base = 0;
int total = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
row[i] += grid[i][j];
col[j] += grid[i][j];
if (grid[i][j]) base += i + j;
total += grid[i][j];
}
}
for (int i = 1; i < m; i++) row[i] += row[i-1];
for (int i = 1; i < n; i++) col[i] += col[i-1];

int res = base;
for (int i = 0; i < m; i++) {
base += i > 0 ? 2 * row[i-1] - total : 0;
int cur = base;
for (int j = 0; j < n; j++) {
cur += j > 0 ? 2 * col[j-1] - total : 0;
res = min(res, cur);
}
}
return res;
}
``````

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