PREFIX SUM › PREFIX SUM
Open — the attempt gate is not wired up yet
This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.
Try it yourself first →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.
| 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. |
#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.
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.
#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;
}
};