Sum of Manhattan distances between all pairs of points

Given n integer coordinates. The task is to find sum of manhattan distance between all pairs of coordinates. 
Manhattan Distance between two points (x₁, y₁) and (x₂, y₂) is: 
|x₁ – x₂| + |y₁ – y₂|
Examples : 

Input : n = 4
        point1 = { -1, 5 }
        point2 = { 1, 6 }
        point3 = { 3, 5 }
        point4 = { 2, 3 }
Output : 22
Distance of { 1, 6 }, { 3, 5 }, { 2, 3 } from 
{ -1, 5 } are 3, 4, 5 respectively.
Therefore, sum = 3 + 4 + 5 = 12

Distance of { 3, 5 }, { 2, 3 } from { 1, 6 } 
are 3, 4 respectively.
Therefore, sum = 12 + 3 + 4 = 19

Distance of { 2, 3 } from { 3, 5 } is 3.
Therefore, sum = 19 + 3 = 22.

Method 1: (Brute Force) 

Time Complexity: O(n²)
The idea is to run two nested loop i.e for each point, find manhattan distance for all other points.  

for (i = 1; i < n; i++)

  for (j = i + 1; j < n; j++)

    sum += ((xi - xj) + (yi - yj))

Below is the implementation of this approach:  

Output:  

22

Time Complexity: O(n²) 
Auxiliary Space: O(1)

Method 2: (Efficient Approach) 

1. The idea is to use Greedy Approach. First observe, the manhattan formula can be decomposed into two independent sums, one for the difference between x coordinates and the second between y coordinates. If we know how to compute one of them we can use the same method to compute the other. So now we will stick to compute the sum of x coordinates distance.
2. Let’s assume that we have calculated the sum of distances between any two points till a point x_i-1 for all values of x‘s smaller than x_i-1 , let this sum be res and now we have to calculate the distance between any two points with x_i included, where x_i is the next greater point, To calculate the distance of each point from the next greater point x_i ,  we can add the existing sum of differences res with the distance of x_i from all the points x_k which are less than x_i. Hence the sum between any two points will now be equal to res + ?(x_i – x_k) , where x_i is the current point from which differences are being measured, and x_k are all the points less than x_i.
3. Because for every calculation x_i remains same, we can simplify the summation as :

res = res + (x_i – x₀) + (x_i – x₁) + (x_i – x₂) + (x_i – x₃)………(x_i – x_i-1)

res = res + (x_i)*i – (x₀ +x₁ + x₂ + …… x_i-1) , because in a sorted array, there are i elements smaller than the current index i .

res = res + (x_i)*i – S_i-1  , where S_i-1 is the sum of all the previous points till index i – 1

        4. For the new index i , we need to add the difference of the current index x_i from all the previous indices x_k  < x_i

        5. If we sort all points in non-decreasing order, we can easily compute the desired sum of distances along one axis between each pair of coordinates in O(N) time, processing points from left to right and using the above method. 
Also, we don’t have to concern if two points are equal coordinates, after sorting points in non-decreasing order, we say that a point x_i-1 is smaller x_i if and only if it appears earlier in the sorted array.
Below is the implementation of this approach: 

Output : 

22

Time Complexity : O(n log n) 
Auxiliary Space: O(1)

This article is contributed by Aarti_Rathi. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above