1685. Sum of Absolute Differences in a Sorted Array

Problem

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.

In other words, result[i] is equal to sum(|nums[i]-nums[j]|) where 0 <= j < nums.length and j != i (0-indexed).

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

Problem Statement

Given a non-decreasing sorted integer array nums. Build and return an integer array result with the same length as nums, such that result[i] is equal to the sum of absolute differences between nums[i] and all other elements in the array. In other words, result[i] is equal to sum(|nums[i]-nums[j]|), where 0 <= j < nums.length and j != i (0-indexed).

Solution

• Use the prefix sum approach to solve the problem. The problem states that the array is sorted, so when calculating absolute values, we can remove the absolute value signs. Suppose we want to calculate the current result[i]. Using i as the boundary, divide the original array nums into 3 parts: nums[0 ~ i-1] and nums[i+1 ~ n]. Every element in the preceding segment nums[0 ~ i-1] is smaller than nums[i]. After removing the absolute value signs, sum(|nums[i]-nums[j]|) = nums[i] * i - prefixSum[0 ~ i-1]. Every element in the following segment nums[i+1 ~ n] is greater than nums[i]. After removing the absolute value signs, sum(|nums[i]-nums[j]|) = prefixSum[i+1 ~ n] - nums[i] * (n - 1 - i). For the special cases, handle i = 0 and i = n separately.

Code

package leetcode

// Solution 1: optimized version prefixSum + sufixSum
func getSumAbsoluteDifferences(nums []int) []int {
	size := len(nums)
	sufixSum := make([]int, size)
	sufixSum[size-1] = nums[size-1]
	for i := size - 2; i >= 0; i-- {
		sufixSum[i] = sufixSum[i+1] + nums[i]
	}
	ans, preSum := make([]int, size), 0
	for i := 0; i < size; i++ {
		// Values that can be added from the back
		res, sum := 0, sufixSum[i]-nums[i]
		res += (sum - (size-i-1)*nums[i])
		// Values that can be added from the front
		res += (i*nums[i] - preSum)
		ans[i] = res
		preSum += nums[i]
	}
	return ans
}

// Solution 2: prefixSum
func getSumAbsoluteDifferences1(nums []int) []int {
	preSum, res, sum := []int{}, []int{}, nums[0]
	preSum = append(preSum, nums[0])
	for i := 1; i < len(nums); i++ {
		sum += nums[i]
		preSum = append(preSum, sum)
	}
	for i := 0; i < len(nums); i++ {
		if i == 0 {
			res = append(res, preSum[len(nums)-1]-preSum[0]-nums[i]*(len(nums)-1))
		} else if i > 0 && i < len(nums)-1 {
			res = append(res, preSum[len(nums)-1]-preSum[i]-preSum[i-1]+nums[i]*i-nums[i]*(len(nums)-1-i))
		} else {
			res = append(res, nums[i]*len(nums)-preSum[len(nums)-1])
		}
	}
	return res
}