Sum Of Absolute Differences In A Sorted Array - Leetcode Solution

Problem Statement:

You are given a sorted integer array nums.

Return the sum of the absolute differences of the elements in nums.

Example 1:

Input: nums = [2,3,5] Output: 4 Explanation: The absolute differences between the elements are:

• [3-2] = 1
• [5-3] = 2
• [5-2] = 3 The sum of these differences is 1 + 2 + 3 = 6.

Example 2:

Input: nums = [1,4,6,8,10] Output: 13

Approach:

Firstly, the sum of absolute differences of the elements in the array can be found by taking the difference between each pair of consecutive elements in the array and adding all the differences. For example, if the array is [2,3,5], the absolute differences will be [3-2, 5-3, 5-2] = [1,2,3] and their sum will be 1+2+3 = 6.

However, for a sorted array, we can come up with a better approach that does not require computing all the differences. We can split the array into two parts where the first part contains all the elements up to index i and the second part contains all the elements from index i+1 onwards. For each element in the first part, we can compute its absolute difference with nums[i] and sum it up. Similarly, for each element in the second part, we can compute its absolute difference with nums[i] and sum it up. Finally, we can add up these two sums to get the total sum of absolute differences.

Solution:

Here's the Python code for implementing the above approach:

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

    # Compute prefix sum
    for i in range(1, n):
        prefix_sum[i] = prefix_sum[i-1] + (nums[i] - nums[i-1]) * i

    # Compute suffix sum
    for i in range(n-2, -1, -1):
        suffix_sum[i] = suffix_sum[i+1] + (nums[i+1] - nums[i]) * (n-i-1)

    # Compute total sum
    result = []
    for i in range(n):
        result.append(prefix_sum[i] + suffix_sum[i])

    return result

Time Complexity:

The time complexity of the above solution is O(n) because we are looping through the array thrice in total to compute the prefix and suffix sums and then to compute the total sum.

Space Complexity:

The space complexity of the above solution is O(n) because we are using two arrays of size n to compute the prefix and suffix sums.

1