Sum of Absolute Differences in a Sorted Array — Solution

Problem

Given a sorted integer array, produce a result array where each position holds the sum of absolute differences between that element and every other element in the array.

Example:

• Input: nums = [2, 3, 5]
• Output: [4, 3, 5]
• Explanation: result[0] = |2−3| + |2−5| = 1 + 3 = 4; result[1] = |3−2| + |3−5| = 1 + 2 = 3; result[2] = |5−2| + |5−3| = 3 + 2 = 5

Intuition

The key insight is that the input is already sorted. Every element to the left of index i is ≤ nums[i], so its absolute difference is just nums[i] − nums[j]. Every element to the right is ≥ nums[i], so its difference is nums[j] − nums[i]. This lets us replace the absolute value with ordinary subtraction on each side, which in turn means a running prefix sum gives us the left contribution in O(1) per index.

Approach 1 — Brute Force

For each element, walk the entire array and accumulate absolute differences directly. No math shortcuts needed.

1. Initialize a result array of length n.
2. For each index i, set a running total to 0.
3. For each index j, add |nums[i] − nums[j]| to the running total.
4. Store the running total in result[i].
5. Return result.

1def sumAbsoluteDifferences(nums: list[int]) -> list[int]:
2    n = len(nums)
3    result = [0] * n
4    for i in range(n):
5        for j in range(n):
6            result[i] += abs(nums[i] - nums[j])
7    return result

Time: O(n²) — every pair (i, j) is visited once.
Space: O(1) extra — only the output array.

Approach 2 — Prefix Sums

Use the sorted order to split each contribution into a left side and a right side, then express both with a running prefix sum in a single pass.

1. Compute the total sum of the array once.
2. Initialize prefix_sum = 0 and iterate left to right.
3. At index i, derive suffix_sum = total − prefix_sum − nums[i].
4. Left contribution: nums[i] appears larger than all i left neighbors, so the sum of differences is nums[i] * i − prefix_sum.
5. Right contribution: nums[i] appears smaller than all (n−1−i) right neighbors, so the sum of differences is suffix_sum − nums[i] * (n − 1 − i).
6. result[i] = left_contribution + right_contribution; then advance prefix_sum by nums[i].

1def sumAbsoluteDifferences(nums: list[int]) -> list[int]:
2    n = len(nums)
3    total = sum(nums)
4    result = [0] * n
5    prefix_sum = 0
6    for i in range(n):
7        left_count = i
8        right_count = n - 1 - i
9        suffix_sum = total - prefix_sum - nums[i]   # sum of all elements to the right of i
10        left_contribution = nums[i] * left_count - prefix_sum   # sorted order: left elems ≤ nums[i]
11        right_contribution = suffix_sum - nums[i] * right_count  # sorted order: right elems ≥ nums[i]
12        result[i] = left_contribution + right_contribution
13        prefix_sum += nums[i]   # update AFTER computing result[i] to exclude nums[i] itself
14    return result

Time: O(n) — a single linear pass plus one sum over the array.
Space: O(1) extra — the prefix sum is maintained as a scalar.

Complexity Summary

Common Mistakes

• Applying the formula to unsorted input: the prefix-sum shortcut assumes every left neighbor is ≤ nums[i] and every right neighbor is ≥ nums[i]. If the array were unsorted, absolute values would no longer cancel cleanly, and the formula would produce wrong results.
• Off-by-one in right_count: there are n − 1 − i elements after index i, not n − i. Using n − i over-counts by one and inflates every right contribution by nums[i].
• Updating prefix_sum before computing result[i]: if you write prefix_sum += nums[i] at the top of the loop body, nums[i] gets subtracted from its own left contribution, giving −nums[i] instead of 0 for that self-term.
• Integer overflow in Java or C++: nums[i] * left_count can exceed 2³¹ − 1 when nums[i] ≈ 10⁵ and left_count ≈ 10⁵. Use long in Java and long long in C++ for intermediate products.
• Forgetting that self-difference is zero: the formula naturally excludes nums[i] from both sides (prefix_sum and suffix_sum both exclude index i), so you don't need a special case for the j == i term — but this is worth verifying when debugging.

Related Problems

• product-of-array-except-self — same left-pass / right-pass split applied to products instead of sums
• subarray-sum-equals-k — prefix sums used to answer range-sum queries in O(1)
• running-sum-of-1d-array — the foundational prefix sum building block
• sum-of-distances-in-tree — the same "sum of distances" concept generalized to a tree with rerooting
• minimum-path-sum — directional accumulation of costs using prefix-style DP