1685. Sum of Absolute Differences in a Sorted Array - Explanation

1. Brute Force

Intuition

For each element, we need to compute the sum of absolute differences with all other elements. Since we need every pair, the straightforward approach is to iterate through every element and compute the difference with every other element, summing them up.

Algorithm

Create a result array res of the same size as nums.
For each index i:
- Initialize sum = 0.
- For each index j:
  - Add |nums[i] - nums[j]| to sum.
- Store sum in res[i].
Return res.

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        res = []

        for i in nums:
            sum = 0
            for j in nums:
                sum += abs(i - j)
            res.append(sum)

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$ for the output array.

2. Prefix & Suffix Sums (Extra Space)

Intuition

Since the array is sorted, we can remove the absolute value operation. For element at index i, all elements to its left are smaller (so we subtract them from nums[i]) and all elements to its right are larger (so we subtract nums[i] from them). Using prefix and suffix sums, we can compute these contributions efficiently without iterating through every pair.

Algorithm

Build a prefix sum array where prefix_sum[i] is the sum of elements from index 0 to i.
Build a suffix sum array where suffix_sum[i] is the sum of elements from index i to n-1.
For each index i:
- Left contribution: i * nums[i] - prefix_sum[i-1] (there are i elements to the left).
- Right contribution: suffix_sum[i+1] - (n - i - 1) * nums[i] (there are n - i - 1 elements to the right).
- Store the sum in res[i].
Return res.

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        n = len(nums)
        prefix_sum = [0] * n
        suffix_sum = [0] * n
        res = [0] * n

        prefix_sum[0] = nums[0]
        for i in range(1, n):
            prefix_sum[i] = prefix_sum[i - 1] + nums[i]

        suffix_sum[n - 1] = nums[n - 1]
        for i in range(n - 2, -1, -1):
            suffix_sum[i] = suffix_sum[i + 1] + nums[i]

        for i in range(n):
            left_sum = (i * nums[i]) - (prefix_sum[i - 1] if i > 0 else 0)
            right_sum = (suffix_sum[i + 1] if i < n - 1 else 0) - ((n - i - 1) * nums[i])
            res[i] = left_sum + right_sum

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Prefix & Suffix Sums

Intuition

We can reduce space by reusing the result array to store suffix sums initially, then computing the final result in a single pass. We first fill the result array with suffix sums, then iterate from left to right, computing the answer for each position while building the prefix sum on the fly.

Algorithm

Initialize the result array with suffix sums by iterating from right to left.
Iterate from left to right, maintaining a running prefix sum:
- Compute left contribution using the running prefix sum.
- Compute right contribution using the precomputed suffix sum at i + 1.
- Store the sum in res[i].
- Update the prefix sum with nums[i].
Return res.

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [0] * n

        res[n - 1] = nums[n - 1]
        for i in range(n - 2, -1, -1):
            res[i] = res[i + 1] + nums[i]

        prefix_sum = 0
        for i in range(n):
            left_sum = (i * nums[i]) - prefix_sum
            right_sum = (res[i + 1] if i < n - 1 else 0) - ((n - i - 1) * nums[i])
            res[i] = left_sum + right_sum
            prefix_sum += nums[i]

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for the output array.

4. Prefix & Suffix Sums (Optimal)

Intuition

Instead of precomputing a suffix sum array, we can compute both prefix and suffix sums on the fly. We start by computing the total sum, then as we iterate through the array, we maintain a running prefix sum and derive the suffix sum by subtracting from the total. This eliminates the need for a separate preprocessing pass.

Algorithm

Compute total_sum of all elements.
Initialize prefix_sum = 0.
For each index i:
- Subtract nums[i] from total_sum to get the suffix sum of elements after index i.
- Compute left contribution: i * nums[i] - prefix_sum.
- Compute right contribution: total_sum - (n - i - 1) * nums[i].
- Store the sum in res[i].
- Add nums[i] to prefix_sum.
Return res.

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [0] * n

        total_sum = sum(nums)
        prefix_sum = 0

        for i, num in enumerate(nums):
            total_sum -= nums[i]
            left_sum = i * nums[i] - prefix_sum
            right_sum = total_sum - (n - i - 1) * nums[i]
            res[i] = left_sum + right_sum
            prefix_sum += nums[i]

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for the output array.

Common Pitfalls

Not Leveraging the Sorted Property

Since the array is sorted, elements to the left of index i are always smaller or equal, and elements to the right are always larger or equal. A common mistake is using abs() for every pair when the sorted property allows us to eliminate the absolute value operation entirely by subtracting left elements from nums[i] and subtracting nums[i] from right elements.

Incorrect Prefix/Suffix Sum Formula

When computing contributions from left and right elements, the formula involves both the count of elements and their sum. For left contribution, it should be i * nums[i] - prefixSum[i-1] (not just the sum). Similarly, for right contribution, it should be suffixSum[i+1] - (n - i - 1) * nums[i]. Mixing up these multipliers leads to wrong results.

Index Out of Bounds at Array Edges

The first element has no left neighbors, and the last element has no right neighbors. Failing to handle these boundary cases by checking i > 0 before accessing prefixSum[i-1] or i < n-1 before accessing suffixSum[i+1] causes index out of bounds errors. Always initialize edge contributions to zero.