Math explained with inductive logic and code with descriptive variable names 🐍 3️⃣.🔟 and 💎
Intuition\nThe way the problem is explained it is automatically O(n^2) this should send off signal flairs that there will be a trick. If we re-examine the condi
# Intuition\nThe way the problem is explained it is automatically $$O(n^2)$$ this should send off signal flairs that there will be a trick. If we re-examine the conditions provided, nums is a strictly increasing array of positive numbers. Is there some [sum?] way to use this information to reduce the time complexity?\n\n\nLuckily the initial example given is a good starting point to think about this. Here is the example again:\n```\nExample 1:\n\nInput: nums = [2,3,5]\nOutput: [4,3,5]\nExplanation: Assuming the arrays are 0-indexed, then\nresult[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,\nresult[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,\nresult[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.\n```\n\nLets pick on `result[1]`.\nresult[1]\n= |3-2| + |3-3| + |3-5|\n= 1 + 0 + 2 \n= 3\n<br/>\nSo what happens here?\n1. We subtract an element less than nums[1]\n2. We subtract an element equal to nums[1]\n3. We subtract an element greater than nums[1]\n** Note this is the only case where absolute value does anything. Here we acutally have to subtract nums[1] from the element to get the right value\n\nSince the array is strictly increasing we can say that elements to the left of i will always be less than nums[i], nums[i] == nums[i], and that all elements to the right of i will always be greater than nums[i].\n\n<br/>\nBy using a prefix sum array and a suffix sum array to keep track of the sum of elements of nums to the left and right of i respectively, we can generalize this to 3 cases:\n\n1. There are i elements to the left of i and they will always be less than nums[i]. This tells us that the absolute sum to the left of i is always nums[i] times the number of elements to the left of i minus the sum of elements left of i.\n*i.e.*\nleft_sum \n= (nums[i] - nums[i - 1]) + (nums[i] - nums[i - 2]) + ... + (nums[i] - nums[0])\n= (nums[i] + nums[i] + ... + nums[i]) - (nums[i - 1] + nums[i - 2] + ... + nums[0])\nleft_sum = nums[i] * i - prefix_sum[i]\n\n2. There is 1 element at i equal to nums[i]. This absolute sum is always 0\n\n3. There are n - i - 1 elements to the right of i and they will always be greater than nums[i]. The absolute sum to the right of i is always the sum of elements to right of i minus nums[i] times the number of elements to the right of i.\n*i.e.*\nright_sum \n= (nums[i + 1] - nums[i] ) + (nums[i + 2] - nums[i] ) + ... + (nums[n] - nums[i] )\n=  (nums[i + 1] + nums[i - 2] + ... + nums[n]) - (nums[i] + nums[i] + ... + nums[i])\nright_sum = suffix_sum[i] - nums[i] * (n - i - 1)\n\nFinally we are left with combining the absolute sum from elements to the left of i, 0, and the absolute sum from elements to the right of i to get the absolute sum of i. We just repeat this process at each element of the array to construct our solution.\n\n# Approach\nInstead of constructing a new O(n) dictionary with prefix and suffix sums of nums (or even worse two lists), we can just use two pointers to keep track of the prefix and suffix sum at each time step.\n\nWe will have to be strategic with when we increment the pointers so that we aren\'t double counting the current index in the left and right sums.\n\nFrom there, the given intuition and the code with it\'s inline comments should be self explanatory. \n\n# Complexity\n- Time complexity:  $$O(n)$$\nRequires two passes of nums: \nonce for the sum.\nonce for the construction of the absolute differences array\n\n- Space complexity: $$O(n)$$\nWe construct a new list of size n to hold absolute differences.\n\n# Code\n\n```python3 []\nclass Solution:\n    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n        n = len(nums)\n        # instead of building prefix and suffix sums, quick compute using pointers\n        sum_to_left, sum_to_right = 0, sum(nums)\n\n        # O(n) time and space complexity\n        abs_diffs = []\n        for index, num in enumerate(nums):\n\n            # calculate abs diff sums for nums less than num\n            left_abs_sum = (num * index) - sum_to_left\n            sum_to_left += num\n\n            # calculate abs diff sums for nums greater than num\n            sum_to_right -= num\n            right_elements = n - index - 1\n            right_abs_sum = sum_to_right - (num * right_elements)\n\n            abs_diffs.append(left_abs_sum + right_abs_sum)\n\n        return abs_diffs\n\n```\n```ruby []\n# @param {Integer[]} nums\n# @return {Integer[]}\ndef get_sum_absolute_differences(nums)\n        n = nums.length\n        sum_to_left, sum_to_right = 0, nums.reduce(0, :+)\n\n        abs_diffs = []\n        nums.each_with_index do |num, index|\n            left_abs_sum = (num * index) - sum_to_left\n\n            sum_to_left += num\n            sum_to_right -= num\n\n            right_elements = n - index - 1\n            right_abs_sum = sum_to_right - (num * right_elements)\n\n            abs_diffs.append(left_abs_sum + right_abs_sum)\n        end\n\n        abs_diffs\nend\n\n```\n$$\\blacksquare$$
['Python3', 'Ruby']