Sum of Absolute Differences in a Sorted Array

medium prefix sum math

Problem

Given a sorted non-decreasing array nums, return result where result[i] = sum over j of |nums[i] − nums[j]|.

Inputnums = [2,3,5]

Output[4,3,5]

i=0: |2-3|+|2-5|=4. i=1: 1+2=3. i=2: 3+2=5.

nums (sorted)

def get_sum_absolute_differences(nums):
    n = len(nums)
    total = sum(nums)
    left = 0
    out = []
    for i, x in enumerate(nums):
        right = total - left - x
        out.append(i * x - left + (right - (n - 1 - i) * x))
        left += x
    return out

function getSumAbsoluteDifferences(nums) {
  const n = nums.length;
  let total = 0;
  for (const x of nums) total += x;
  let left = 0;
  const out = new Array(n);
  for (let i = 0; i < n; i++) {
    const x = nums[i];
    const right = total - left - x;
    out[i] = i * x - left + (right - (n - 1 - i) * x);
    left += x;
  }
  return out;
}

class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        int n = nums.length;
        long total = 0;
        for (int x : nums) total += x;
        long left = 0;
        int[] out = new int[n];
        for (int i = 0; i < n; i++) {
            long x = nums[i];
            long right = total - left - x;
            out[i] = (int) (i * x - left + (right - (n - 1 - i) * x));
            left += x;
        }
        return out;
    }
}

vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
    int n = nums.size();
    long total = 0;
    for (int x : nums) total += x;
    long left = 0;
    vector<int> out(n);
    for (int i = 0; i < n; i++) {
        long x = nums[i];
        long right = total - left - x;
        out[i] = (int)(i * x - left + (right - (long)(n - 1 - i) * x));
        left += x;
    }
    return out;
}

Explanation

Because the array is sorted, the absolute-value bars disappear: every element to the left of i is smaller and every element to the right is larger. That lets us split result[i] into a left part and a right part and compute both with running sums instead of a nested loop.

For the left side there are i elements, each <= nums[i], so their combined distance is i * nums[i] - left, where left is the sum of those i elements. For the right side there are n-1-i larger elements, so their distance is right - (n-1-i) * nums[i], where right is the sum of everything after i.

We keep total (the sum of all values) and a running left that grows as we move right; right = total - left - x. After using x, we add it into left for the next index. No extra prefix array is even needed.

Example: nums = [2,3,5]. For i=0: left part is 0, right part is (3+5) - 2*2 = 4. For i=1: (1*3 - 2) + ((5) - 1*3) = 1 + 2 = 3. For i=2: all on the left, 2*5 - (2+3) = 5. Result [4,3,5].

Each index is handled in constant work, so the whole array is computed in O(n).

Time: O(n) Space: O(n)