[Java/Python 3] Prefix Sum O(n) code w/ brief explanation and analysis.
Absolute difference between two ints = the bigger - the smaller. Therefore, \n\nres[i] = (nums[i] - nums[0]) + (nums[i] - nums[1]) + ... + (nums[i] - nums[i - 1
Absolute difference between two ints = the bigger - the smaller. Therefore, \n```\nres[i] = (nums[i] - nums[0]) + (nums[i] - nums[1]) + ... + (nums[i] - nums[i - 1])        <--- absolute difference of nums[i] with first i numbers\n     + (nums[i] - nums[i]) + (nums[i + 1] - nums[i]) + (nums[i + 2] - nums[i]) + ... + (nums[n - 1] - nums[i])   <--- absolute difference of nums[i] with last n - i numbers\n```\nafter simplification:\n```\nres[i] = i * nums[i] - (nums[0] + ... + nums[i - 1])        <--- absolute difference of nums[i] with first i numbers\n     + (nums[i + 1] + ... + nums[n]) - (n - i) * nums[i]   <--- absolute difference of nums[i] with last n - i numbers\n```\nThat is\n```\nres[i] = i * nums[i] - prefixSum[i]\nprefixSum[n] - prefixSum[i] - (n - i) * nums[i]\n```\n\n```java\n    public int[] getSumAbsoluteDifferences(int[] nums) {\n        int n = nums.length;\n        int[] res = new int[n];\n        int[] prefixSum = new int[n + 1];\n        for (int i = 0; i < n; ++i) {\n            prefixSum[i + 1] = prefixSum[i] + nums[i];\n        }\n        for (int i = 0; i < n; ++i) {\n            res[i] = i * nums[i] - prefixSum[i] + (prefixSum[n] -  prefixSum[i] - (n - i) * nums[i]);\n        }\n        return res;\n    }\n```\n```python\n    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n        n, prefix_sum, res = len(nums), [0], []\n        for num in nums:\n            prefix_sum += [num + prefix_sum[-1]]\n        for i, num in enumerate(nums):\n            res += [i * num - prefix_sum[i] + prefix_sum[n] - prefix_sum[i] - (n - i) * num]    \n        return res\n```\n**Analysis:**\n\nTime & space: `O(n)`, where `n = nums.length`.\n\n----\n\n\nWe can further optimize the above to space `O(1)` codes: - credit to **@mittalvaibhav1**\n```java\n    public int[] getSumAbsoluteDifferences(int[] nums) {\n        int n = nums.length, leftSum = 0, rightSum = Arrays.stream(nums).sum();\n        int[] res = new int[n];\n        for (int i = 0; i < n; ++i) {\n            res[i] = i * nums[i] - leftSum + rightSum - (n - i) * nums[i];\n            leftSum += nums[i];\n            rightSum -= nums[i];\n        }\n        return res;\n    }\n```\n```python\n    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n        left_sum, right_sum, res, n = 0, sum(nums), [], len(nums)\n        for i, num in enumerate(nums):\n            res.append(i * num - left_sum + right_sum - (n - i) * num)\n            left_sum += num\n            right_sum -= num\n        return res\n```\n**Analysis:**\n\nTime: `O(n)`, space: `O(1)`, where `n = nums.length`.
[]