Watch 10 video solutions for Sum of Absolute Differences in a Sorted Array, a medium level problem involving Array, Math, Prefix Sum. This walkthrough by NeetCodeIO has 12,675 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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).
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]
Constraints:
2 <= nums.length <= 1051 <= nums[i] <= nums[i + 1] <= 104Problem Overview: You receive a sorted integer array nums. For every index i, compute the sum of |nums[i] - nums[j]| for all other elements. Because the array is already sorted, values to the left are always smaller and values to the right are always larger. That ordering removes the need to compute absolute values individually.
Approach 1: Naive Pairwise Calculation (O(n²) time, O(1) space)
Iterate through each index i and compute the sum of absolute differences with every other element. This means a nested loop: the outer loop fixes nums[i], while the inner loop accumulates |nums[i] - nums[j]| for all j. The method uses only constant extra memory but performs n * n operations. It works for any array and clearly demonstrates the definition of the problem, but it becomes too slow when n grows large.
Approach 2: Prefix Sum Optimization (O(n) time, O(n) space)
The sorted property lets you separate contributions from the left and right sides. For index i, all elements before it are smaller. Their total difference equals nums[i] * i - leftSum. All elements after it are larger, contributing rightSum - nums[i] * (n - i - 1). Maintain prefix sums to quickly compute leftSum and derive rightSum from the total array sum. This removes the inner loop entirely and reduces the problem to a single pass.
The key insight: instead of computing each absolute difference separately, aggregate them using arithmetic derived from ordering. Prefix sums store cumulative totals so each index can evaluate both sides in constant time. This pattern appears frequently in problems involving cumulative distances or cost aggregation.
Conceptually, the algorithm works like this: compute the total sum, iterate once through the array, maintain a running prefix sum, and use simple multiplication to determine how much each side contributes. The final answer for each position is the sum of the left contribution and the right contribution.
Problems like this commonly combine Array traversal with Prefix Sum precomputation and a bit of arithmetic reasoning from Math. Recognizing that the array is sorted is the turning point that enables the linear solution.
Recommended for interviews: Interviewers expect the prefix sum approach. The brute force solution shows you understand the definition of absolute differences, but the optimized O(n) method demonstrates that you recognize patterns in sorted arrays and know how to convert repeated calculations into prefix-sum formulas.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Pairwise Calculation | O(n²) | O(1) | Useful for understanding the problem definition or when input size is very small |
| Prefix Sum Optimization | O(n) | O(n) | Best choice when the array is sorted and you need a scalable solution |