Sum of Absolute Differences in a Sorted Array — Editorial

Opening the reading…

Intuitionsorted order removes the absolute-value case split

For a fixed index i, every element to its left is no larger than nums[i]. Its absolute difference is therefore nums[i] - nums[j]. Every element to its right is no smaller, so its difference is nums[j] - nums[i]. The sorted order changes one absolute-value sum into two ordinary sums: the distance to everything on the left plus the distance to everything on the right.

The left distances add up to nums[i] multiplied by the number of left elements, minus the sum of those elements. The right distances use the same pattern in reverse: the sum of the right elements minus nums[i] multiplied by their count. If you know the sum before i and the total sum, you can obtain both sides without comparing nums[i] with any element individually.

A running prefix sum supplies the left sum before the answer is computed. The total sum supplies the right sum after removing the prefix and nums[i] itself. This lets each index use constant work, while the running sum is updated only after the current index has finished using it.

Approachderive both sides before adding the current value

Compute the total sum of nums once, because the right-side sum can then be obtained by subtracting the values already passed and the current value.

Start prefixSum at zero, representing the sum of elements at indices strictly smaller than the current index; including nums[i] too early would corrupt the left contribution.

For each index i, set leftCount to i and rightCount to n - i - 1, because those are exactly the numbers of elements on the two sides and the current element must not contribute to itself.

Calculate leftSum as nums[i] * leftCount - prefixSum, because each left element is smaller or equal and its distance is nums[i] minus that element.

Calculate the sum of the right side as totalSum - prefixSum - nums[i], then subtract nums[i] * rightCount to obtain the right distances; removing nums[i] prevents the current element from being counted as a neighbor.

Store leftSum + rightSum in result[i], since the problem asks for all left and right distances combined.

Add nums[i] to prefixSum after storing the answer, so the next index sees the current value as part of its left side.

Complexitythe output is required storage, not working memory

MEASURE	BOUND	WHY
Time	O(n)	The total-sum pass examines each element once and the answer pass examines each element once. Each index uses a fixed number of arithmetic operations, so no element participates in a nested comparison or repeated scan.
Space	O(1) extra	The returned result array is required output and is excluded from the extra-space bound. Apart from it, the solution stores only counts, sums, and loop variables, so the working memory stays constant even for the worst allowed input shape.

Here n is the length of nums.

Annotated solutionC++ · one running prefix sum · constant extra space

CPPCompute the total once, then combine left and right contributions during one scan.

#include <vector>
using namespace std;

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

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

        int prefixSum = 0;
        for (int i = 0; i < n; ++i) {
            int leftCount = i;
            int rightCount = n - i - 1;

            int leftSum = nums[i] * leftCount - prefixSum;
            int rightValues = totalSum - prefixSum - nums[i];
            int rightSum = rightValues - nums[i] * rightCount;

            result[i] = leftSum + rightSum;
            prefixSum += nums[i];
        }

        return result;
    }
};

The placement of prefixSum += nums[i] is the key detail. At the start of index i, prefixSum must describe indices 0 to i - 1, because the formula for the left side excludes the current element. After result[i] is complete, nums[i] becomes part of the prefix for index i + 1. The right side follows the same exclusion rule by removing nums[i] from the total explicitly.

The two-array version trades memory for visible boundariesa different arrangement, not a faster algorithm

You can also build prefix and suffix sums explicitly. For each index, prefix[i] stores the sum before i and suffix[i] stores the sum after i, making the two formulas look almost exactly like their mathematical definitions. This version still takes O(n) time, but it uses O(n) extra working space in addition to the returned array. It is useful when several later calculations need the same side sums.

CPPStore the sum before and after every index explicitly, then apply the two contribution formulas.

#include <vector>
using namespace std;

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

        for (int i = 1; i < n; ++i) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }

        for (int i = n - 2; i >= 0; --i) {
            suffix[i] = suffix[i + 1] + nums[i + 1];
        }

        for (int i = 0; i < n; ++i) {
            int leftSum = nums[i] * i - prefix[i];
            int rightCount = n - i - 1;
            int rightSum = suffix[i] - nums[i] * rightCount;
            result[i] = leftSum + rightSum;
        }

        return result;
    }
};