We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Absolute Differences in a Sorted Array

Number: 1787

Difficulty: Medium

Paid? No

Companies: Adobe

Problem Description

Given a non-decreasing sorted integer array nums, build and return an integer array result of the same length such that result[i] is equal to the summation of the absolute differences between nums[i] and all the other elements in the array. In other words, result[i] equals the sum of |nums[i] - nums[j]| for all j (0-indexed) where j ≠ i.

Key Insights

  • Since the array is sorted, the absolute difference between any two elements can be divided into two parts: differences from elements on the left and differences from elements on the right.
  • Utilize a prefix sum array to quickly compute the sum of elements to the left and the right of a specific index.
  • For an index i:
    • The contribution from the left = nums[i] * i - (sum of elements before i).
    • The contribution from the right = (sum of elements after i) - nums[i] * (number of elements after i).

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in the array, due to a single pass to compute the prefix sum and a subsequent pass to compute the differences. Space Complexity: O(n) for storing the prefix sum array and the final result array.

Solution

We use a prefix sum approach to efficiently compute the sum of all differences. First, compute a prefix sum array where prefix[i+1] contains the sum of the first i numbers. Then, for each index i, calculate:

  • Left sum difference as: nums[i] * i - prefix[i]
  • Right sum difference as: (prefix[n] - prefix[i+1]) - nums[i] * (n - i - 1) The final result at index i is the sum of these two computed values.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with detailed line-by-line comments.

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        n = len(nums)
        # Build the prefix sum array where prefix[i+1] is the sum of first i elements
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + nums[i]
        # Initialize result array to hold the final answers
        result = [0] * n
        # Calculate the absolute differences for each index
        for i in range(n):
            # For left side: each element contributes nums[i] minus its value
            left = nums[i] * i - prefix[i]
            # For right side: subtract nums[i] from each element to the right
            right = (prefix[n] - prefix[i+1]) - nums[i] * (n - i - 1)
            result[i] = left + right
        return result
← Back to All Questions