Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1685. Sum of Absolute Differences in a Sorted Array - Leetcode Solution

Code Implementation

class Solution:
    def getSumAbsoluteDifferences(self, nums):
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + nums[i]
        res = []
        for i in range(n):
            left = i * nums[i] - prefix[i]
            right = (prefix[n] - prefix[i+1]) - (n - i - 1) * nums[i]
            res.append(left + right)
        return res
      
class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix(n + 1, 0);
        for (int i = 0; i < n; ++i)
            prefix[i+1] = prefix[i] + nums[i];
        vector<int> res(n);
        for (int i = 0; i < n; ++i) {
            int left = i * nums[i] - prefix[i];
            int right = (prefix[n] - prefix[i+1]) - (n - i - 1) * nums[i];
            res[i] = left + right;
        }
        return res;
    }
};
      
class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; ++i)
            prefix[i+1] = prefix[i] + nums[i];
        int[] res = new int[n];
        for (int i = 0; i < n; ++i) {
            int left = i * nums[i] - prefix[i];
            int right = (prefix[n] - prefix[i+1]) - (n - i - 1) * nums[i];
            res[i] = left + right;
        }
        return res;
    }
}
      
var getSumAbsoluteDifferences = function(nums) {
    let n = nums.length;
    let prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i)
        prefix[i+1] = prefix[i] + nums[i];
    let res = new Array(n);
    for (let i = 0; i < n; ++i) {
        let left = i * nums[i] - prefix[i];
        let right = (prefix[n] - prefix[i+1]) - (n - i - 1) * nums[i];
        res[i] = left + right;
    }
    return res;
};

Problem Description

Given a nums array of integers sorted in non-decreasing order, you are asked to compute, for each index i, the sum of absolute differences between nums[i] and every other element in the array. In other words, for each index i, compute:

result[i] = |nums[i] - nums[0]| + |nums[i] - nums[1]| + ... + |nums[i] - nums[n-1]|

Constraints:
  • The array nums is sorted in non-decreasing order.
  • Each element must be considered for the sum except for itself, but since |nums[i] - nums[i]| = 0, including it does not affect the sum.
  • All elements must be included in the calculation; do not skip or reuse elements.
  • The solution should be efficient for large arrays (up to 105 elements).

Thought Process

At first glance, this problem seems to require calculating the absolute difference between every pair of elements, for every index. This would mean, for each i, looping through the array and summing up the differences, resulting in a brute-force approach with O(n2) time complexity.

However, the key observation is that the array is already sorted. This property allows us to optimize the calculation because:
  • For elements before i, nums[i] - nums[j] is always non-negative.
  • For elements after i, nums[j] - nums[i] is always non-negative.
By leveraging prefix sums and the sorted property, we can compute the sum of absolute differences for each index efficiently, instead of recalculating the same differences multiple times.

Solution Approach

To solve the problem efficiently, we use the following approach:
  1. Calculate Prefix Sums: Build a prefix sum array prefix where prefix[i] is the sum of the first i elements of nums. This allows us to quickly compute the sum of any subarray.
  2. For Each Index, Split the Work: For each index i:
    • Left Side: For all j < i, the sum of differences is (i * nums[i] - prefix[i]). This comes from the fact that there are i elements before i, and each difference is nums[i] - nums[j].
    • Right Side: For all j > i, the sum of differences is ((prefix[n] - prefix[i+1]) - (n - i - 1) * nums[i]). Here, prefix[n] - prefix[i+1] is the sum of all elements after i, and each difference is nums[j] - nums[i].
  3. Combine Both Sides: Add the left and right sums to get the total sum of absolute differences for index i.
  4. Return the Result: Store the computed values in the result array and return it.
This approach ensures we only need O(n) time, as prefix sums are computed in O(n) and each index is processed in constant time.

Example Walkthrough

Let's walk through the algorithm with an example input:

Input: nums = [2, 3, 5]

Step 1: Compute Prefix Sums
  • prefix[0] = 0
  • prefix[1] = 2
  • prefix[2] = 2 + 3 = 5
  • prefix[3] = 5 + 5 = 10
So prefix = [0, 2, 5, 10].

Step 2: Calculate for Each Index
  • i = 0:
    Left: 0 * 2 - 0 = 0
    Right: (10 - 2) - (3 - 0 - 1) * 2 = 8 - 2*2 = 8 - 4 = 4
    Total: 0 + 4 = 4
  • i = 1:
    Left: 1 * 3 - 2 = 3 - 2 = 1
    Right: (10 - 5) - (3 - 1 - 1) * 3 = 5 - 1*3 = 5 - 3 = 2
    Total: 1 + 2 = 3
  • i = 2:
    Left: 2 * 5 - 5 = 10 - 5 = 5
    Right: (10 - 10) - (3 - 2 - 1) * 5 = 0 - 0*5 = 0
    Total: 5 + 0 = 5
Output: [4, 3, 5]

This matches the expected result.

Time and Space Complexity

  • Brute-force Approach: For each index, compare to every other index, leading to O(n2) time and O(1) extra space.
  • Optimized Approach (Prefix Sums):
    • Time Complexity: O(n) — We compute prefix sums in O(n), and each index is processed in O(1).
    • Space Complexity: O(n) — For the prefix sum array and the result array.
The optimized approach is much more efficient and suitable for large input sizes.

Summary

To efficiently compute the sum of absolute differences for each element in a sorted array, we leverage prefix sums and the sorted property. This allows us to split the problem into manageable parts (left and right of each index) and avoid redundant calculations. The result is a clean, O(n) solution that is both elegant and practical for large datasets.