Skip to content

1685. Sum of Absolute Differences in a Sorted Array

SourceBiweekly Contest 41 Q2DifficultyMediumRating1495

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.

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

Solutions

Solution 1: Summation + Enumeration

Thinking

The array is sorted, so \(\lvert x-y \rvert\) is \(x-y\) on the left and \(y-x\) on the right. Each \(i\)'s sum of absolute differences is \(O(1)\) from the left and right sums.

With total sum \(s\) and scanned sum \(t\), \(\textit{ans}[i]=x\cdot i-t+(s-t)-x\cdot(n-i)\), then add \(x\) into \(t\).

First, we calculate the sum of all elements in the array \(\textit{nums}\), denoted as \(s\). We use a variable \(t\) to record the sum of the elements that have been enumerated so far.

Next, we enumerate \(\textit{nums}[i]\). Then \(\textit{ans}[i] = \textit{nums}[i] \times i - t + s - t - \textit{nums}[i] \times (n - i)\). After that, we update \(t\), i.e., \(t = t + \textit{nums}[i]\). We continue to enumerate the next element until all elements are enumerated.

The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{nums}\).

1
2
3
4
5
6
7
8
9
class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        ans = []
        s, t = sum(nums), 0
        for i, x in enumerate(nums):
            v = x * i - t + s - t - x * (len(nums) - i)
            ans.append(v)
            t += x
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        // int s = Arrays.stream(nums).sum();
        int s = 0, t = 0;
        for (int x : nums) {
            s += x;
        }
        int n = nums.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            int v = nums[i] * i - t + s - t - nums[i] * (n - i);
            ans[i] = v;
            t += nums[i];
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int s = accumulate(nums.begin(), nums.end(), 0), t = 0;
        int n = nums.size();
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            int v = nums[i] * i - t + s - t - nums[i] * (n - i);
            ans[i] = v;
            t += nums[i];
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func getSumAbsoluteDifferences(nums []int) (ans []int) {
    var s, t int
    for _, x := range nums {
        s += x
    }
    for i, x := range nums {
        v := x*i - t + s - t - x*(len(nums)-i)
        ans = append(ans, v)
        t += x
    }
    return
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function getSumAbsoluteDifferences(nums: number[]): number[] {
    const s = nums.reduce((a, b) => a + b);
    let t = 0;
    const n = nums.length;
    const ans = new Array(n);
    for (let i = 0; i < n; ++i) {
        const v = nums[i] * i - t + s - t - nums[i] * (n - i);
        ans[i] = v;
        t += nums[i];
    }
    return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var getSumAbsoluteDifferences = function (nums) {
    const s = nums.reduce((a, b) => a + b);
    let t = 0;
    const n = nums.length;
    const ans = new Array(n);
    for (let i = 0; i < n; ++i) {
        const v = nums[i] * i - t + s - t - nums[i] * (n - i);
        ans[i] = v;
        t += nums[i];
    }
    return ans;
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public class Solution {
    public int[] GetSumAbsoluteDifferences(int[] nums) {
        int s = 0, t = 0;
        foreach (int x in nums) {
            s += x;
        }
        int n = nums.Length;
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            int v = nums[i] * i - t + s - t - nums[i] * (n - i);
            ans[i] = v;
            t += nums[i];
        }
        return ans;
    }
}

Comments