O(n) Linear time complexity using Python
Solution by Rockposedon\n#\n## Approach: PrefixSum & SuffixSum\n#\n### Intuition\nThis solution utilizes the PrefixSum and SuffixSum techniques to efficiently c
# **Solution by** [**Rockposedon**](https://leetcode.com/Rockposedon/)\n#\n## **Approach: PrefixSum & SuffixSum**\n#\n### Intuition\nThis solution utilizes the PrefixSum and SuffixSum techniques to efficiently calculate the sum of absolute differences for each element in the array. The key idea is to precompute the prefix sum and suffix sum arrays, which allows us to calculate the left and right sums for each element in linear time.\n#\n### Implementation\n1. Initialize arrays for prefix sum and suffix sum.\n2. Calculate the prefix sum by iterating through the array from left to right.\n3. Calculate the suffix sum by iterating through the array from right to left.\n4. Iterate through the array and calculate the left and right sums using the precomputed prefix and suffix sums.\n5. Assemble the total sum of absolute differences and return the result.\n#\n### Time Complexity\nThe time complexity of this solution is O(n), where n is the size of the input array. The use of prefix sum and suffix sum optimizes the computation of left and right sums.\n\n```python\nclass Solution:\n    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n        n = len(nums)\n        prefix_sum = [0] * n\n        suffix_sum = [0] * n\n\n        # Calculate prefix sum\n        prefix_sum[0] = nums[0]\n        for i in range(1, n):\n            prefix_sum[i] = prefix_sum[i - 1] + nums[i]\n\n        # Calculate suffix sum\n        suffix_sum[n - 1] = nums[n - 1]\n        for i in range(n - 2, -1, -1):\n            suffix_sum[i] = suffix_sum[i + 1] + nums[i]\n\n        result = []\n        for i in range(n):\n            # Calculate left and right sums efficiently using prefix and suffix sums\n            left_sum = i * nums[i] - prefix_sum[i]\n            right_sum = suffix_sum[i] - (n - i - 1) * nums[i]\n\n            # Calculate the total sum of absolute differences\n            result.append(left_sum + right_sum)\n\n        return result\n-----------------------------------------------------------------------------------------------------\n\n\t\t\t\tIf you find this solution helpful, consider giving it an upvote! \uD83D\uDC4D\n\t\t\t\t\n-----------------------------------------------------------------------------------------------------\n
['Prefix Sum', 'Python3']