Sum of Absolute Differences in a Sorted Array

How it works

Instead of precomputing a suffix sum array, we can compute both prefix and suffix sums on the fly. We start by computing the total sum, then as we iterate through the array, we maintain a running prefix sum and derive the suffix sum by subtracting from the total. This eliminates the need for a separate preprocessing pass.

Steps

1. Compute total_sum of all elements.
2. Initialize prefix_sum = 0.
3. For each index i:
   • Subtract nums[i] from total_sum to get the suffix sum of elements after index i.
   • Compute left contribution: i * nums[i] - prefix_sum.
   • Compute right contribution: total_sum - (n - i - 1) * nums[i].
   • Store the sum in res[i].
   • Add nums[i] to prefix_sum.
4. Return res.

Complexity

• Time complexity: O(n)
• Space complexity: O(n) for the output array.

Things to watch for

Not Leveraging the Sorted Property

Since the array is sorted, elements to the left of index i are always smaller or equal, and elements to the right are always larger or equal. A common mistake is using abs() for every pair when the sorted property allows us to eliminate the absolute value operation entirely by subtracting left elements from nums[i] and subtracting nums[i] from right elements.

Incorrect Prefix/Suffix Sum Formula

When computing contributions from left and right elements, the formula involves both the count of elements and their sum. For left contribution, it should be i * nums[i] - prefixSum[i-1] (not just the sum). Similarly, for right contribution, it should be suffixSum[i+1] - (n - i - 1) * nums[i]. Mixing up these multipliers leads to wrong results.

Index Out of Bounds at Array Edges

The first element has no left neighbors, and the last element has no right neighbors. Failing to handle these boundary cases by checking i > 0 before accessing prefixSum[i-1] or i < n-1 before accessing suffixSum[i+1] causes index out of bounds errors. Always initialize edge contributions to zero.

from typing import List

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [0] * n

        total_sum = sum(nums)
        prefix_sum = 0

        for i, num in enumerate(nums):
            total_sum -= nums[i]
            left_sum = i * nums[i] - prefix_sum
            right_sum = total_sum - (n - i - 1) * nums[i]
            res[i] = left_sum + right_sum
            prefix_sum += nums[i]

        return res

class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 0);

        int totalSum = 0, prefixSum = 0;
        for (int& num : nums) {
            totalSum += num;
        }

        for (int i = 0; i < n; i++) {
            totalSum -= nums[i];
            int leftSum = i * nums[i] - prefixSum;
            int rightSum = totalSum - (n - i - 1) * nums[i];
            res[i] = leftSum + rightSum;
            prefixSum += nums[i];
        }

        return res;
    }
};