Distance Metrics with O(n) Complexity

For each element in a given array, calculate the absolute value of index differences between it and all other elements of the same value.

a = [1, 9, 9, 7, 7, 1, 9]

r[0] = |5-0| = 5
r[1] = |2-1| + |6-1| = 6
r[2] = |2-1| + |6-2| = 5
r[3] = |4-3| = 1
r[4] = |4-3| = 1
r[5] = |5-0| = 5
r[6] = |6-1| + |6-2| = 9

Python 3

def get_distance_metrics(numbers):
    from collections import defaultdict

    buckets = defaultdict(list)

    for index, number in enumerate(numbers):
        buckets[number].append(index)

    r = [None] * len(numbers)

    for indexes in buckets.values():
        left_len = 0
        right_len = len(indexes)

        left_sum = 0
        right_sum = sum(indexes)

        for index in indexes:
            right_len -= 1
            right_sum -= index

            r[index] = right_sum - left_sum - (right_len-left_len)*index

            left_len += 1
            left_sum += index

    return r

items = [1, 9, 9, 7, 7, 1, 9]
print(get_distance_metrics(items))
# [5, 6, 5, 1, 1, 5, 9]

Sum of Absolute Differences in a sorted Array

For each element in a sorted array, calculate the absolute differences between it and all other elements.

items = [a0, a1, a2, a3, a4, a5]

r[0] = (a5 - a0) + (a4 - a0) + (a3 - a0) + (a2 - a0) + (a1 - a0)
= (a5 + a4 + a3 + a2 + a1) - (5-0)*a0

r[1] = (a5 - a1) + (a4 - a1) + (a3 - a1) + (a2 - a1) + -(a0 - a1)
= (a5 + a4 + a3 + a2) - (a0) - (4-1)*a1

r[2] = (a5 - a2) + (a4 - a2) + (a3 - a2) + -(a1 -a2) + -(a0 - a2)
= (a5 + a4 + a3) - (a0 + a1) - (3-2)*a2

Python 3

def get_sum_of_abs_diff(sorted_list):
    left_len = 0
    right_len = len(sorted_list)

    left_sum = 0
    right_sum = sum(sorted_list)

    r = [None] * len(sorted_list)

    for index, number in enumerate(sorted_list):
        right_len -= 1
        right_sum -= number

        r[index] = right_sum - left_sum - (right_len-left_len)*number

        left_len += 1
        left_sum += number

    return r

# sorted list
items = [1, 2, 3, 4, 5]

# O(n^2)
print([sum(abs(i - j) for j in items) for i in items])
# [10, 7, 6, 7, 10]

# O(n)
print(get_sum_of_abs_diff(items))
# [10, 7, 6, 7, 10]