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.
The naive approach involves calculating the summation of absolute differences directly for each element. For each element `nums[i]` in the array, iterate through every other element `nums[j]` and accumulate the absolute difference `|nums[i] - nums[j]|`. This results in a straightforward solution but with a time complexity of O(n^2) due to the nested loops.
This C solution initializes an array to store the results. For each element in the input array, it calculates the sum of absolute differences by iterating through the entire array and applying the abs function. The result for each element is stored in the result array.
Time Complexity: O(n^2) where n is the length of the array.
Space Complexity: O(n) for the result array.
To optimize the solution, use prefix sums to reduce redundant calculations. Compute prefix sums `leftSum` and `rightSum` to capture cumulative totals on each side of the current index. For each nums[i], compute the contribution using:
i, each number nums[j] contributes to |nums[i] - nums[j]| as nums[i] - nums[j].i to end, each number nums[j] contributes as nums[j] - nums[i].This C implementation uses cumulative `leftSum` and `rightSum` to keep track of elements processed. By adjusting these sums and using the formula, we efficiently calculate the results in O(n) time.
Time Complexity: O(n) as each element is processed only twice.
Space Complexity: O(n) to store the result.
First, we calculate the sum of all elements in the array nums, denoted as s. We use a variable t to record the sum of the elements that have been enumerated so far.
Next, we enumerate nums[i]. Then ans[i] = nums[i] times i - t + s - t - nums[i] times (n - i). After that, we update t, i.e., t = t + nums[i]. We continue to enumerate the next element until all elements are enumerated.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
JavaScript
C#
| Approach | Complexity |
|---|---|
| Naive Approach | Time Complexity: |
| Optimized Using Prefix Sums | Time Complexity: |
| Summation + Enumeration | — |
| 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 |
Sum of Absolute Differences in a Sorted Array - Leetcode 1685 - Python • NeetCodeIO • 12,675 views views
Watch 9 more video solutions →Practice Sum of Absolute Differences in a Sorted Array with our built-in code editor and test cases.
Practice on FleetCode