Soultion with O(n) Time and Space complexity. Uses Prefix Sum. 3 ms Beats 99.36% of users with Java.
Intuition\nThe problem involves calculating the sum of absolute differences for each element in an array. One way to approach this is by using prefix sums to ef
# Intuition\nThe problem involves calculating the sum of absolute differences for each element in an array. One way to approach this is by using prefix sums to efficiently compute the cumulative sum of elements. The idea is to iterate through the array, maintaining the prefix sum at each index. Then, for each element, compute the sum of absolute differences based on the prefix sums.\n\n# Approach\nCalculate the prefix sum of the input array to efficiently obtain the cumulative sum at each index.\n\nIterate through the array and, for each element at index i, compute the sum of absolute differences using the prefix sums.\n\nUpdate the input array with the calculated sum of absolute differences.\n\n# Complexity\n- Time complexity: O(n)\nThe algorithm iterates through the array twice, once for calculating the prefix sum and once for updating the array. Both iterations have a linear time complexity.\n\n- Space complexity: O(n)\nAdditional space is used for the prefixSum array, which has the same length as the input array. The overall space complexity is linear.\n# Code\n```\nclass Solution {\n    public int[] getSumAbsoluteDifferences(int[] nums) {\n        int len = nums.length;\n        int[] prefixSum = new int[len + 1];\n        prefixSum[0] = 0;\n        int sum = 0;\n        int index = 1;\n        for (int i = 0; i < len; i++) {\n            sum += nums[i];\n            prefixSum[index] = sum;\n            index++;\n        }\n        for (int i = 0; i < len; i++) {\n            int x = (prefixSum[len] - prefixSum[i]) - (nums[i] * (len - i));\n            int y = (nums[i] * i) - prefixSum[i];\n            nums[i] = x + y;\n        }\n        return nums;\n    }\n}\n```
['Math', 'Prefix Sum', 'Java']