relative_manhattan_distance.py

from typing import List

class Solution:

    def bruteforce_distances(self, arr: List[int]) -> List[int]:
        distances = [0]*len(arr)
        for i, a in enumerate(arr):
            distance = 0
            for a_ in arr:
                distance += abs(a - a_)
            distances[i] = distance
        return distances

    # arr is sorted
    def distances(self, arr: List[int]) -> List[int]:
        n = len(arr)
        if n < 2:
            return [0]*n
        relative_distances = [ arr[i]-arr[i-1] for i in range(1, n) ]
        forward, backward = [0]*n, [0]*n
        for i in range(1, n):
            forward[i] = forward[i-1] + i*relative_distances[i-1]
            backward[n-i-1] = backward[n-i] + i*relative_distances[n-i-1]
        sum_distances = [0]*n
        for i in range(n):
            sum_distances[i] = forward[i] + backward[i]
        return sum_distances

if __name__ == "__main__":
    solution = Solution()
    testcases = [
        [0,0,0,0,0,0,0,0,0,0,0],
        [1,2,3,4,5,6,7,8,9,10],
        [1,4,7,12,64,67,123],
        [1,1,2,2,3,3,4,4,5,5,6,6,7,7,7],
        [0,1,2,4,8,16,32,64,128,256],
        [100],
        [],
        [100,200],
        [100,200,300]
    ]

    for testcase in testcases:
        print("Testcase: ", testcase)
        print("bruteforce", solution.bruteforce_distances(testcase))
        print("efficient ", solution.distances(testcase))
        print()