# 6ms C++ one pass O(mn) solution no sort, Easiest Solution O(n) + O(m) extra space

• Because it is Manhattan Distance, horizontal distance, and vertical distance is independent of each other.
In another word move the meeting point to another row ( vertically ) will not affect the horizontal total distance.

For example the test cast:
1 - 0 - 0 - 0 - 1
0 - 0 - 0 - 0 - 0
0 - 0 - 1 - 0 - 0

will be the same to calculate two 1D distance
horizontal distance 1 - 0 - 1 - 0 - 1
vertical distance 2 - 0 - 1

Then we do not need to sort of put index value on the list.
You only need to use two pointers to find the correct position.
1 - 0 - 1 - 0 - 1 is the same if we deduct both sides by 1
0 - 0 - 1 - 0 - 0 because the 5 distance from house 1 and house 5 can not be avoided.

2 - 0 - 1 is the same is the same if we deduct both sides by the smaller one.
1 - 0 - 0 because the 3 distance * (number of house) also can not be avoided.
Then you just calculated the distance and add it together.

int minTotalDistance(vector<vector<int>>& grid) {
vector<int> horizontal(grid.size()), vertical(grid[0].size());
for (int row = 0; row < (int) horizontal.size(); row++){
for (int column = 0; column < (int) vertical.size(); column++){
horizontal[row] += grid[row][column];
vertical[column] += grid[row][column];
}
}
int hDistance = Solution::minTotalDistance(horizontal);
int vDistance = Solution::minTotalDistance(vertical);
return hDistance + vDistance;
}
int minTotalDistance(vector<int>& list){
vector<int> temp = list;
int left = 0, right = list.size() - 1;
while (left < right) {
if (temp[left] == 0) left++;
else if (temp[right] == 0) right--;
else if (temp[left] < temp[right])
{
temp[right] -= temp[left];
left++;
}
else if (temp[left] == temp[right])
{
left++; right--;
}
else
{
temp[left] -= temp[right];
right--;
}
}
int distance = 0;
for (int i = 0; i < (int) list.size(); i++)
{
distance += abs(i-left)*list[i];
}
return distance;
}

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