Problem Description

The problem asks to compute the sum of absolute differences between each element in a sorted integer array and all other elements in the array. The result should be an array of the same length as the input, where each element represents this sum of absolute differences for the corresponding element in the input array.

Solution Explanation

The most efficient solution leverages the sorted nature of the input array to avoid brute-force O(n^2) calculations. The core idea is to calculate the sum of absolute differences efficiently using prefix sums and some mathematical manipulations.

Let's analyze the absolute difference calculation for a single element nums[i]:

sum(|nums[i] - nums[j]|) for all j != i

This can be broken down into two parts:

1. Sum of differences with elements smaller than nums[i]: This is equivalent to nums[i] * i - sum(nums[0...i-1]). The nums[i] * i part accounts for the difference between nums[i] and each of the i elements smaller than it. sum(nums[0...i-1]) is the sum of the smaller elements.

2. Sum of differences with elements larger than nums[i]: This is equivalent to sum(nums[i+1...n-1]) - nums[i] * (n - i -1). sum(nums[i+1...n-1]) is the sum of larger elements, and nums[i] * (n - i -1) accounts for subtracting nums[i] from each of the larger elements.

By pre-calculating the total sum (s) of all elements in the array and maintaining a running sum (t) of elements up to the current index, we can efficiently compute these two parts for each nums[i]. The final formula becomes:

ans[i] = nums[i] * i - t + s - t - nums[i] * (n - i)

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the input array. This is because we iterate through the array once to calculate the total sum and once more to calculate the sum of absolute differences for each element.

• Space Complexity: O(1) (or O(n) depending on the implementation). The solution uses a constant amount of extra space to store variables like s, t, and the result array ans. Some implementations might use additional space proportional to n if creating a new array for results is considered.

Code Implementation (Python)

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        n = len(nums)
        s = sum(nums)  # Total sum of elements
        t = 0          # Running sum of elements up to current index
        ans = []
        for i, x in enumerate(nums):
            v = x * i - t + s - t - x * (n - i) #Efficient Calculation
            ans.append(v)
            t += x
        return ans

This Python code directly implements the optimized algorithm described above. Similar implementations can be easily done in other languages like Java, C++, Javascript, etc., maintaining the same time and space complexity. The core logic remains the same across all languages.