Sum of Absolute Differences in a Sorted Array — Solution
Sum of Absolute Differences in a Sorted Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Sum of Absolute Differences in a Sorted Array is a medium coding problem on arrays, math and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Math, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
nums is sorted in non-decreasing order.
Return an array result of the same length where result[i] is the sum of |nums[i] - nums[j]| over every index j of the array (the term for j = i is zero).
Example 1
Input: nums = [2,5,9]
Output: [10,7,11]
Explanation: `result[1] = |5-2| + |5-5| + |5-9| = 3 + 0 + 4 = 7`.
Example 2
Input: nums = [1,1,4]
Output: [3,3,6]
Example 3
Input: nums = [7,7]
Output: [0,0]
Constraints
2 <= nums.length <= 10^51 <= nums[i] <= nums[i + 1] <= 10^4
Hints for Sum of Absolute Differences in a Sorted Array
Hint 1
Because the array is sorted, every element left of
iis at mostnums[i]and every element right of it is at leastnums[i].Hint 2
So the left part contributes
nums[i] * i - (sum of the left elements)and the right part(sum of the right elements) - nums[i] * (count on the right).Hint 3
Keep a running prefix sum and the total; each
result[i]is then O(1).
How to solve Sum of Absolute Differences in a Sorted Array
Sorting removes the absolute values: to the left of i every difference is nums[i] - nums[j], to the right it is nums[j] - nums[i], and both sides collapse into prefix-sum formulas.
Approach
- Compute
total, the sum of all elements, and sweepiwithleft, the sum ofnums[0..i-1]. right = total - left - nums[i]is the sum ofnums[i+1..n-1].result[i] = nums[i] * i - left + right - nums[i] * (n - 1 - i).- Add
nums[i]toleftand continue.
Why it works
For j < i, nums[j] <= nums[i], so |nums[i] - nums[j]| = nums[i] - nums[j]; summing over the i such indices gives nums[i] * i - left. The right side is symmetric. Together they are exactly the requested sum.
Complexity
- Time —
O(n) - Space —
O(1) besides the output
Pitfalls
- The double loop is O(n^2) — too slow for 10^5 elements.
- Mind the counts:
ielements on the left,n - 1 - ion the right. - Each result is at most about 10^9 here, which fits in 32 bits; use 64-bit intermediates if the bounds grow.
Reference solution
Python
from typing import List
def getSumAbsoluteDifferences(nums: List[int]) -> List[int]:
n = len(nums)
total = sum(nums)
left = 0
result = []
for i, x in enumerate(nums):
right = total - left - x
result.append(x * i - left + right - x * (n - 1 - i))
left += x
return resultJava
public static int[] getSumAbsoluteDifferences(int[] nums) {
int n = nums.length;
long total = 0, left = 0;
for (int v : nums) total += v;
int[] result = new int[n];
for (int i = 0; i < n; i++) {
long x = nums[i];
long right = total - left - x;
result[i] = (int) (x * i - left + right - x * (n - 1 - i));
left += x;
}
return result;
}C++
vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
int n = nums.size();
long long total = 0, left = 0;
for (int v : nums) total += v;
vector<int> result(n);
for (int i = 0; i < n; i++) {
long long x = nums[i];
long long right = total - left - x;
result[i] = (int)(x * i - left + right - x * (n - 1 - i));
left += x;
}
return result;
}JavaScript
var getSumAbsoluteDifferences = function(nums) {
var n = nums.length, total = 0, left = 0;
for (var i = 0; i < n; i++) total += nums[i];
var result = new Array(n);
for (var j = 0; j < n; j++) {
var x = nums[j];
var right = total - left - x;
result[j] = x * j - left + right - x * (n - 1 - j);
left += x;
}
return result;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Prefix Sum