1685. Sum of Absolute Differences in a Sorted Array

LeetCode Problem

This is a tricky question, but it is not hard to solve. The key is prefix sum.

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        n = len(nums)
        prefix_sum = [nums[0]]
        for i in range(1, n):
            prefix_sum.append(prefix_sum[-1] + nums[i])
        results = []
        for i in range(n):
            left_sum = prefix_sum[i] - nums[i]
            right_sum = prefix_sum[-1] - prefix_sum[i]
            left_count = i
            right_count = n - i - 1
            results.append(left_count * nums[i] - left_sum + right_sum - right_count * nums[i])
        return results