§ Sum of absolute differences of an array

• We are given an array a[:] and we are asked to compute the sum of differences $\sum_{i=1}^n \sum_{j=i+1}^n |a[i] - a[j]|$.
• To compute this efficiently, first sort a[:] into a sorted array s[:]. For simplicity, say we have N = 4.
• Now see that if we write down the values for N=4, we will see:

D =
|s[1] - s[2]| + |s[1] - s[3]| + |s[1] - s[4]| +
|s[2] - s[3]| + |s[2] - s[4]| +
|s[3] - s[4]|

• i < j implies s[i] < s[j] as s is sorted. So each of the terms (s[i] - s[j]|) is negative. We thus flip the terms, giving:

D =
(s[2] - s[1]) + (s[3] - s[1]) + (s[4] - s[1]) +
(s[3] - s[2]) + (s[4] - s[2]) +
(s[4] - s[3])

• Note that s[1] is always negative, so it will have coefficient -4 on grouping.
• See that s[2] was positive in the grouping (1, 2), and was negative in the groupings (2, 3) and (2, 4). So 2 will have a coefficient +1*(2-1) -1*(4 - 2).
• Similarly, s[3] was positive in the grouping (1, 3) and (2, 3) and was negative in the grouping (3, 4).
• In general, s[i] will be positive when paired with [1, 2, ..i-1, i) and negative when paired with (i, i+1, i+2, \dots n]. So s[i] will contribute a coefficient of +1*(i-1) - 1*(n-i)[using the formula that for intervals [l, r) and (l, r] the number of elements is (r-l)]