Sum of Absolute Differences in a Sorted Array

MEDIUM

Description

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 <= 10⁵
1 <= nums[i] <= nums[i + 1] <= 10⁴

Approaches

Checkout 3 different approaches to solve Sum of Absolute Differences in a Sorted Array. Click on different approaches to view the approach and algorithm in detail.

Brute Force

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 result array of the same size as nums.
Use a nested loop structure. The outer loop iterates through each element nums[i] from i = 0 to n-1.
The inner loop iterates through each element nums[j] from j = 0 to n-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 each i.
After the inner loop completes, assign currentSum to result[i].
After the outer loop finishes, return the result array.

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 Analysis

Time Complexity: 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 Complexity: O(N) to store the output array. If the output array is not considered extra space, the complexity is O(1).

Pros and Cons

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.

Code Solutions

Checking out 5 solutions in different languages for Sum of Absolute Differences in a Sorted Array. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Sum of Absolute Differences in a Sorted Array

Patterns:

MathPrefix Sum

Data Structures:

Array