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.
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; }}Video 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.