Sum Of Absolute Differences In A Sorted Array

TARGET DECK: Leetcode FILE TAGS: Medium

Todo

Optimize this question like was done in Product of Array Except Self.

---

Intuition

• This question boils down to a formula.
• For a given index, that index is subtracted by all the other elements.
• Since the array is sorted, we can take advantage of this fact by noticing:
  • All elements that come before the index (the prefix[i - 1]) are less then the current element, and therefore, the current element should subtract those elements.
  • Likewise, all elements that come after the current element (postfix[i + 1]) are greater than the current element, and so those elements should subtract the current element.
• We use prefix and postfix here since similarly to Product of Array Except Self, we care about the prefix which is the

Complexity

Runtime

$O(N)$

Space

$O(N)$ to build the prefix and postfix arrays, respectively.

Code

Cleaned Up Somewhat

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        n = len(nums)
        prefix = [nums[0]] + [0] * (n - 1)
        postfix = [0] * (n - 1) + [nums[-1]]
        for i in range(1, n):
            prefix[i] = prefix[i - 1] + nums[i]
            postfix[n - i - 1] = nums[n - i - 1] + postfix[n - i]
        
        res = []
        for i in range(n):
            cur_res = 0
            if i != 0:
                cur_res += i * nums[i] - prefix[i - 1]
            if i != n - 1:
                cur_res += postfix[i + 1] - (n - i - 1) * nums[i]
            res.append(cur_res)
            
        return res

Using Axillary Prefix and Postfix

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        n = len(nums)
        prefix = [nums[0]]
        for i in range(1, n):
            prefix.append(prefix[i - 1] + nums[i])
        
        postfix = [0] * n
        postfix[-1] = nums[-1]
        for i in range(n - 2, -1, -1):
            postfix[i] = nums[i] + postfix[i + 1]
 
        res = []
        for i in range(n):
            cur_res = 0
            if i != 0:
                cur_res += i * nums[i] - prefix[i - 1]
            if i != n - 1:
                cur_res += postfix[i + 1] - (n - i - 1) * nums[i]
            res.append(cur_res)
            
        return res

Notes

Cards

START Basic Front: Sum Of Absolute Differences In A Sorted Array Back: ${\text{res}}_i={\sum }_j|a_j-a_i|={\sum }_{i<j}(a_j-a_i)+{\sum }_{j<i}(a_i-a_j)$

END

---

References

• Sum Of Absolute Differences In A Sorted Array