Sum of Absolute Differences in a Sorted Array
MediumUpdated: Aug 2, 2025
Practice on:
Problem
You are given an integer array nums sorted in non-decreasing order.
Build and return an integer array result with the same length as nums such that result[i] is equal to the summation of absolute differences between nums[i] and all the other elements in the array.
In other words, result[i] is equal to sum(|nums[i]-nums[j]|) where 0 <= j < nums.length and j != i (0-indexed).
Examples
Example 1:
Input:
nums = [2,3,5]
Output:
[4,3,5]
Explanation: Assuming the arrays are 0-indexed, then
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.
Example 2:
Input:
nums = [1,4,6,8,10]
Output:
[24,15,13,15,21]
Solution
Method 1 - Wrong Solution with Sum
One solution can be we sum up all the numbers, and
ans[i] = sum - nums[i];
Let's see some examples to see why it is not valid:
nums = [2,3,5]
sum = 10
for 2: |10 - 2 * 3| = |2 - 2 + 3 - 2 + 5 - 2| = |8 - 4| = 4
for 3: |10 - 3 * 3| = |2 - 3 + 3 - 3 + 5 - 3| = |7 - 6| = 1
for 5: |10 - 5 * 3| = |2 - 5 + 3 - 5 + 5 - 5| = |5 - 10| = 5
Code
Java
public int[] getSumAbsoluteDifferences(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
long sum = Arrays.stream(nums).reduce(0, Integer::sum);
for (int i = 0; i < n; i++) {
ans[i] = Math.abs((int) (sum - n * nums[i]));
}
return ans;
}
Complexity
- Time:
O(n) - Space:
O(1)
Method 2 - Using Prefix and Suffix Sum
Intuition
We use prefix and suffix sums to efficiently compute the sum of absolute differences for each index. By precomputing cumulative sums from both ends, we can calculate the left and right contributions for each element in constant time.
Approach
- Compute prefix sums and suffix sums for the array.
- For each index
i, calculate:- Left: sum of differences with all elements before
i. - Right: sum of differences with all elements after
i.
- Left: sum of differences with all elements before
- Combine left and right to get the result for each index.
Complexity
- ⏰ Time complexity:
O(n) - 🧺 Space complexity:
O(n)
Code
C++
class Solution {
public:
vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
int n = nums.size();
vector<int> prefix(n), suffix(n);
prefix[0] = nums[0];
suffix[n-1] = nums[n-1];
for (int i = 1; i < n; ++i) {
prefix[i] = prefix[i-1] + nums[i];
suffix[n-i-1] = suffix[n-i] + nums[n-i-1];
}
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
int left = nums[i] * i - prefix[i];
int right = suffix[i] - nums[i] * (n - i - 1);
ans[i] = left + right;
}
return ans;
}
}
Go
func getSumAbsoluteDifferences(nums []int) []int {
n := len(nums)
prefix := make([]int, n)
suffix := make([]int, n)
prefix[0] = nums[0]
suffix[n-1] = nums[n-1]
for i := 1; i < n; i++ {
prefix[i] = prefix[i-1] + nums[i]
suffix[n-i-1] = suffix[n-i] + nums[n-i-1]
}
ans := make([]int, n)
for i := 0; i < n; i++ {
left := nums[i]*i - prefix[i]
right := suffix[i] - nums[i]*(n-i-1)
ans[i] = left + right
}
return ans
}
Java
class Solution {
public int[] getSumAbsoluteDifferences(int[] nums) {
int n = nums.length;
int[] prefixSum = new int[n];
int[] suffixSum = new int[n];
prefixSum[0] = nums[0];
suffixSum[n - 1] = nums[n - 1];
for (int i = 1; i < n; ++i) {
prefixSum[i] = prefixSum[i - 1] + nums[i];
suffixSum[n - i - 1] = suffixSum[n - i] + nums[n - i - 1];
}
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
int left = nums[i] * i - prefixSum[i];
int right = suffixSum[i] - nums[i] * (n - i - 1);
ans[i] = left + right;
}
return ans;
}
}
Kotlin
class Solution {
fun getSumAbsoluteDifferences(nums: IntArray): IntArray {
val n = nums.size
val prefix = IntArray(n)
val suffix = IntArray(n)
prefix[0] = nums[0]
suffix[n-1] = nums[n-1]
for (i in 1 until n) {
prefix[i] = prefix[i-1] + nums[i]
suffix[n-i-1] = suffix[n-i] + nums[n-i-1]
}
val ans = IntArray(n)
for (i in 0 until n) {
val left = nums[i] * i - prefix[i]
val right = suffix[i] - nums[i] * (n - i - 1)
ans[i] = left + right
}
return ans
}
}
Python
class Solution:
def getSumAbsoluteDifferences(self, nums):
n = len(nums)
prefix = [0] * n
suffix = [0] * n
prefix[0] = nums[0]
suffix[n-1] = nums[n-1]
for i in range(1, n):
prefix[i] = prefix[i-1] + nums[i]
suffix[n-i-1] = suffix[n-i] + nums[n-i-1]
ans = [0] * n
for i in range(n):
left = nums[i] * i - prefix[i]
right = suffix[i] - nums[i] * (n - i - 1)
ans[i] = left + right
return ans
Rust
struct Solution;
impl Solution {
pub fn get_sum_absolute_differences(nums: Vec<i32>) -> Vec<i32> {
let n = nums.len();
let mut prefix = vec![0; n];
let mut suffix = vec![0; n];
prefix[0] = nums[0];
suffix[n-1] = nums[n-1];
for i in 1..n {
prefix[i] = prefix[i-1] + nums[i];
suffix[n-i-1] = suffix[n-i] + nums[n-i-1];
}
let mut ans = vec![0; n];
for i in 0..n {
let left = nums[i] * i as i32 - prefix[i];
let right = suffix[i] - nums[i] * (n as i32 - i as i32 - 1);
ans[i] = left + right;
}
ans
}
}
Typescript
class Solution {
getSumAbsoluteDifferences(nums: number[]): number[] {
const n = nums.length;
const prefix = Array(n).fill(0);
const suffix = Array(n).fill(0);
prefix[0] = nums[0];
suffix[n-1] = nums[n-1];
for (let i = 1; i < n; ++i) {
prefix[i] = prefix[i-1] + nums[i];
suffix[n-i-1] = suffix[n-i] + nums[n-i-1];
}
const ans = Array(n).fill(0);
for (let i = 0; i < n; ++i) {
const left = nums[i] * i - prefix[i];
const right = suffix[i] - nums[i] * (n - i - 1);
ans[i] = left + right;
}
return ans;
}
}