57. Sum of Absolute Differences in Sorted Array

Given a sorted integer array nums, return an array result where result[i] is the sum of absolute differences between nums[i] and every other element in the array.

Input: A sorted integer array nums of length n.

Output: Integer array result where result[i] = sum of |nums[i]-nums[j]| for all j.

Examples

Input: [2,3,5]
Output: [4,3,5]
Explanation: result[0]=|2-3|+|2-5|=1+3=4. result[1]=|3-2|+|3-5|=1+2=3. result[2]=|5-2|+|5-3|=3+2=5.

Input: [1,4,6,8,10]
Output: [24,15,13,15,24]
Explanation: Use prefix sums for O(n) computation.

Input: [1,2,3]
Output: [3,2,3]
Explanation: result[0]=|1-2|+|1-3|=1+2=3. result[1]=1+1=2. result[2]=2+1=3.

Constraints

• 2<=nums.length<=10^5
• 1<=nums[i]<=10^4
• nums is sorted in non-decreasing order.

Asked by