Sum of Absolute Differences in a Sorted Array
MedPrompt
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] <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward method is to directly implement the problem's definition. For each element nums[i], we can iterate through the entire array nums again, calculate the absolute difference with every other element nums[j], and sum these differences up. This gives us the value for result[i].
Algorithm
- Initialize a
resultarray of the same size asnums. - Use a nested loop structure. The outer loop iterates through each element
nums[i]fromi = 0ton-1. - The inner loop iterates through each element
nums[j]fromj = 0ton-1. - Inside the inner loop, calculate the absolute difference
|nums[i] - nums[j]|. - Add this difference to a running sum variable, say
currentSum, which is initialized to 0 for eachi. - After the inner loop completes, assign
currentSumtoresult[i]. - After the outer loop finishes, return the
resultarray.
Walkthrough
This approach uses a nested loop. The outer loop selects an element nums[i], and the inner loop iterates over all elements nums[j] in the array. For each pair (i, j), we compute Math.abs(nums[i] - nums[j]) and add it to a temporary sum. Once the inner loop is finished, this sum is the value for result[i]. This process is repeated for every element in the nums array.
class Solution { public int[] getSumAbsoluteDifferences(int[] nums) { int n = nums.length; int[] result = new int[n]; for (int i = 0; i < n; i++) { int currentSum = 0; for (int j = 0; j < n; j++) { currentSum += Math.abs(nums[i] - nums[j]); } result[i] = currentSum; } return result; }}Complexity
Time
O(N^2), where N is the number of elements in `nums`. For each of the N elements, we perform another N operations inside the inner loop.
Space
O(N) to store the output array. If the output array is not considered extra space, the complexity is O(1).
Trade-offs
Pros
Very simple to understand and implement directly from the problem statement.
Cons
Highly inefficient for large inputs due to its quadratic time complexity.
Will likely cause a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
A more efficient approach leverages the fact that the input array nums is sorted. This allows us to remove the absolute value from the calculation by splitting the sum into two parts: the sum of differences with elements to the left and the sum of differences with elements to the right. We can use a prefix sum array to quickly find the sum of elements in any subarray.
Algorithm
- First, create a prefix sum array, let's call it
prefix, of sizen+1. - Iterate through
numsto populateprefix, whereprefix[i]stores the sum of the firstielements ofnums. So,prefix[i+1] = prefix[i] + nums[i]. - The total sum of all elements,
totalSum, will beprefix[n]. - Create a
resultarray of sizen. - Iterate from
i = 0ton-1:- The sum of elements to the left of
iisleftSum = prefix[i]. - The sum of elements to the right of
iisrightSum = totalSum - prefix[i+1]. - The number of elements to the left is
leftCount = i. - The number of elements to the right is
rightCount = n - 1 - i. - Calculate
result[i] = (leftCount * nums[i] - leftSum) + (rightSum - rightCount * nums[i]).
- The sum of elements to the left of
- Return the
resultarray.
Walkthrough
Since nums is sorted, for any nums[i], all elements nums[j] with j < i are less than or equal to nums[i], and all elements nums[j] with j > i are greater than or equal to nums[i]. The formula for result[i] can be expanded as:
result[i] = sum(nums[i] - nums[j]) for j < i + sum(nums[j] - nums[i]) for j > i.
This simplifies to:
result[i] = (i * nums[i] - sum_left) + (sum_right - (n-1-i) * nums[i]).
To get sum_left (sum of elements before i) and sum_right (sum of elements after i) efficiently, we can precompute a prefix sum array. This allows us to find these sums in O(1) time for each i.
class Solution { public int[] getSumAbsoluteDifferences(int[] nums) { int n = nums.length; int[] prefixSum = new int[n + 1]; for (int i = 0; i < n; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } int[] result = new int[n]; int totalSum = prefixSum[n]; for (int i = 0; i < n; i++) { int leftSum = prefixSum[i]; int rightSum = totalSum - prefixSum[i + 1]; int leftCount = i; int rightCount = n - 1 - i; int leftTotal = leftCount * nums[i] - leftSum; int rightTotal = rightSum - rightCount * nums[i]; result[i] = leftTotal + rightTotal; } return result; }}Complexity
Time
O(N), as it involves a pass to build the prefix sum array and another pass to compute the results.
Space
O(N) to store the prefix sum array and the result array.
Trade-offs
Pros
Significantly faster than the brute-force approach with a linear time complexity.
Efficient enough to pass the given constraints.
Cons
Requires additional space proportional to the input size for the prefix sum array.
This approach is an optimization of the prefix sum method. Instead of pre-calculating and storing the entire prefix sum array, we can achieve the same result in a single pass with constant extra space. We do this by dynamically maintaining the sum of elements to the left (leftSum) and calculating the sum of elements to the right (rightSum) on the fly.
Algorithm
- First, iterate through the
numsarray once to calculate thetotalSumof all its elements. - Initialize a
resultarray of sizenand aleftSumvariable to 0. - Iterate through the
numsarray fromi = 0ton-1:- Calculate the
rightSumfor the current elementnums[i]using the formula:rightSum = totalSum - leftSum - nums[i]. - The number of elements to the left is
leftCount = i. - The number of elements to the right is
rightCount = n - 1 - i. - Calculate
result[i]using the same formula as the prefix sum approach:result[i] = (leftCount * nums[i] - leftSum) + (rightSum - rightCount * nums[i]). - After calculating
result[i], updateleftSumfor the next iteration by adding the current element:leftSum += nums[i].
- Calculate the
- Return the
resultarray.
Walkthrough
The mathematical formula for result[i] remains the same: result[i] = (i * nums[i] - leftSum) + (rightSum - (n - 1 - i) * nums[i]). We start by calculating the totalSum of the array. Then, we iterate through the array, maintaining a leftSum variable. In each step i, leftSum holds the sum of elements nums[0] through nums[i-1]. The rightSum can then be found by subtracting leftSum and the current element nums[i] from totalSum. After calculating result[i], we update leftSum by adding nums[i] to it, making it ready for the next iteration. This avoids the need for an O(N) prefix sum array.
class Solution { public int[] getSumAbsoluteDifferences(int[] nums) { int n = nums.length; int totalSum = 0; for (int num : nums) { totalSum += num; } int[] result = new int[n]; int leftSum = 0; for (int i = 0; i < n; i++) { int rightSum = totalSum - leftSum - nums[i]; int leftCount = i; int rightCount = n - 1 - i; int leftTotal = leftCount * nums[i] - leftSum; int rightTotal = rightSum - rightCount * nums[i]; result[i] = leftTotal + rightTotal; leftSum += nums[i]; } return result; }}Complexity
Time
O(N). We make one pass to get the total sum and another pass to compute the results, leading to an overall linear time complexity.
Space
O(1) extra space. We only use a few variables to keep track of sums. The O(N) space for the output array is generally not counted as extra space.
Trade-offs
Pros
Optimal solution with linear time complexity.
Space-efficient, using only constant extra space (excluding the output array).
Cons
The logic can be slightly less intuitive to derive compared to the more direct brute-force or prefix sum array approaches.
Solutions
Solution
public class Solution { public int[] GetSumAbsoluteDifferences(int[] nums) { int s = 0, t = 0; foreach(int x in nums) { s += x; } int n = nums.Length; int[] ans = new int[n]; for (int i = 0; i < n; ++i) { int v = nums[i] * i - t + s - t - nums[i] * (n - i); ans[i] = v; t += nums[i]; } return ans; }}class Solution {public int[] getSumAbsoluteDifferences(int[] nums) {/** * @param {number[]} nums * @return {number[]} */ var getSumAbsoluteDifferences = function (nums) { const s = nums.reduce((a, b) => a + b); let t = 0; const n = nums.length; const ans = new Array(n); for (let i = 0; i < n; ++i) { const v = nums[i] * i - t + s - t - nums[i] * (n - i); ans[i] = v; t += nums[i]; } return ans; };class Solution {public: vector<int> getSumAbsoluteDifferences(vector<int> &nums) { int s = accumulate(nums.begin(), nums.end(), 0), t = 0; int n = nums.size(); vector<int> ans(n); for (int i = 0; i < n; ++i) { int v = nums[i] * i - t + s - t - nums[i] * (n - i); ans[i] = v; t += nums[i]; } return ans; }};class Solution: def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]: ans = [] s, t = sum(nums), 0 for i, x in enumerate(nums): v = x * i - t + s - t - x * (len(nums) - i) ans . append(v) t += x return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.