Description

You are given an integer array nums sorted in non-decreasing order.

Build and return an integer array result with the same length as nums such that result[i] is equal to the summation of absolute differences between nums[i] and all the other elements in the array.

Example 1:

Input: nums = [2,3,5] Output: [4,3,5] Explanation: Assuming the arrays are 0-indexed, then result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4, result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3, result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5. Example 2:

Input: nums = [1,4,6,8,10] Output: [24,15,13,15,21]

Constraints:

2 <= nums.length <= 105 1 <= nums[i] <= nums[i + 1] <= 104

Solution

Since the array is sorted. We can take off the absolute symbol easily. We can also use the accumulated sum to calculate the partial sum of the array.

Below is the implementation

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        '''
        i*nums[i] - sum[0, i- 1] + sum[i + 1, n - 1] - (n - 1 - i) * nums[i]
        '''
        acc = 0
        accs = [0]
        for num in nums:
            acc += num
            accs.append(acc)
        ret = []
        n = len(nums)
        ret = []
        for i in range(n):
            r = i * nums[i] - (accs[i] - accs[0]) + (accs[n] - accs[i + 1]) - (n - 1 - i) * nums[i]
            ret.append(r)
        return ret