# 8ms c++ solution, O(n) + O(m) extra space, O(mn) time

• Hi,

The idea is to count the total number of home in each row and column, calculating the distance to each horizontal / vertical point. The point is that the distance can be separately measured for the horizontal and vertical directions, and the optimal point can also be chosen separately.

``````class Solution {
public:
int minTotalDistance(vector<vector<int>>& grid) {
if (grid.size() == 0 || grid[0].size() == 0)
return 0;
int m = grid.size();
int n = grid[0].size();

int ver_cnts[m];
fill_n(ver_cnts, m, 0);
int c = 0;

// count hor_cnts, ver_cnts
int hor_cnts[n];
fill_n(hor_cnts, n, 0);
for (vector<int> &row: grid)  {
int ver_cnt = 0;
for (int i = 0; i < n; i++) {
hor_cnts[i] += row[i];
ver_cnt += row[i];
}

ver_cnts[c++] = ver_cnt;
}

// get the cost to each hor potition
// hor: the cost of moving horizontally to each column
int hor[n];
fill_n(hor, n, 0);

// forward
int hor_temp[n];
hor_temp[0] = 0;
int cnt = hor_cnts[0];
for (int i = 1; i < n; i++) {
hor_temp[i] = hor_temp[i-1] + cnt;
cnt += hor_cnts[i];
}
for (int i = 0; i < n; i++) {
hor[i] += hor_temp[i];
}

// backward
hor_temp[n-1] = 0;
cnt = hor_cnts[n-1];
for (int i = n-2; i >= 0; i--) {
hor_temp[i] = hor_temp[i+1] + cnt;
cnt += hor_cnts[i];
}
// pick up the optimal col
int min_h_val = INT_MAX;
for (int i = 0; i < n; i++) {
hor[i] += hor_temp[i];
if (hor[i] < min_h_val) {
min_h_val = hor[i];
}
}

// get the cost to each ver potition
// ver: the cost of moving vertically to each row
int ver[m];
fill_n(ver, m, 0);

// forward
int ver_temp[m];
ver_temp[0] = 0;
cnt = ver_cnts[0];
for (c = 1; c < m; c++) {
ver_temp[c] = ver_temp[c-1] + cnt;
cnt += ver_cnts[c];
}
for (c = 0; c < m; c++) {
ver[c] += ver_temp[c];
}

//backward
ver_temp[m-1]= 0;
cnt = ver_cnts[m-1];
for (c = m-2; c >= 0; c--) {
ver_temp[c] = ver_temp[c+1] + cnt;
cnt += ver_cnts[c];
}
// pick up the optimal row
int min_v_val = INT_MAX;
for (c = 0; c < m; c++) {
ver[c] += ver_temp[c];
if (ver[c] < min_v_val) {
min_v_val = ver[c];
}
}

return min_h_val + min_v_val;
}
};``````

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