Sum of Absolute Differences in a Sorted Array

Problem 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).

Key Insights

• The absolute difference |a - b| can be efficiently computed using properties of sorted arrays.
• For a given index i, all elements to the left are less than or equal to nums[i] and all elements to the right are greater than or equal to nums[i].
• The total contribution of each element can be computed using prefix sums to avoid repeated calculations.
• The result for each index can be derived by using cumulative sums to efficiently calculate the sum of differences.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can utilize prefix sums to efficiently compute the sum of absolute differences. The key steps in the algorithm are as follows:

1. Create a prefix sum array where each element at index i contains the sum of the elements of nums up to index i.
2. For each index i in nums, calculate the total absolute differences using the prefix sum:
   • For elements to the left of i, their contribution is calculated as i * nums[i] - prefix_sum[i-1].
   • For elements to the right of i, their contribution is calculated as prefix_sum[n-1] - prefix_sum[i] - (n - i - 1) * nums[i], where n is the length of nums.
3. Combine the contributions from both sides to compute result[i].

Code Solutions