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


  • 0
    S

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

Log in to reply
 

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