Beats 100% | Intuition Explained | Java O(n) | Prefix and Suffix Sum | Easy Approach
Intuition\n Describe your first thoughts on how to solve this problem. \nWe see that we are given a sorted array. So there must be some reason that the array is
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe see that we are given a sorted array. So there must be some reason that the array is sorted. We are told to find the absolute difference between the current element and all other elements.\nSeeing that the array is sorted, we can say that-\n- Elements above i(current element) would be greater that $$nums[i]$$.\n- Elements below i would be less than $$nums[i]$$.\n\nSo let\'s divide the array into two parts, left and right of current element.\n\nNOTE: We can\'t just take the total sum and subtract it from $$ nums[i]*length$$ of array because left elements would yield a negative answer and right elements would give a positive answer.\neg:\n```\narr = [2, 3, 5]\nif i = 1\nans = |10 - 9| = 1 //wrong\nans = |2 - 3| + |3 - 3| + |3 - 5| = 3 //correct\n//we get a negative answer from left and positive from right \n//hence if we take the total sum, it would be wrong\n```\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- First find the total sum of the array.\n- Initialize left sum as 0 and right sum as the total sum.\n- take $$l = nums.length-1$$ to count the right elements.\n- Now iterate the array and first decrease the right sum with nums[i]. This will give us the correct right sum for that index.\n- Now result would be equal to $$rightSum - nums[i] * l + nums[i]*i - leftSum$$. $$i$$ denotes the number of left elements.\n- Increment the $$leftSum$$ and decrease $$l$$.\n- Note that now we don\'t need absolute value as all values will come out positive.\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n```\nclass Solution {\n    public int[] getSumAbsoluteDifferences(int[] nums) {\n        int i, leftSum = 0, rightSum, sum = 0, l;\n\n        for(i=0;i<nums.length;i++) {\n            sum += nums[i];\n        }\n\n        int[] res = new int[nums.length];\n\n        rightSum = sum;\n        l = nums.length-1;\n\n        for(i=0;i<nums.length;i++) {\n            rightSum -= nums[i];\n            res[i] = (rightSum - nums[i]*l) + (nums[i]*i - leftSum);\n            leftSum += nums[i];\n            l--;\n        }\n        return res;\n    }\n}\n```
['Java']