Simplest C++ Explained Solution PrefixSum and SuffixSum Approach 💡
Problem\nThe array is sorted. I will tell how it is.\n\n# Introduction\nCreate an array with the same length as nums, and store the sub of absolute difference b
# Problem\nThe array is sorted. I will tell how it is.\n\n# Introduction\nCreate an array with the same length as nums, and store the sub of absolute difference between the current and all other elements.\n\nLet\'s take an example\n```\nnums[] = [1,2,4,5];\n```\nFor index 0, calculate the sum of absolute difference between 1 and all other elements (2,4,5).\n```\nindex = 0, elem = 1;\n\n| 1 - 2 | = 1;\n| 1 - 4 | = 3;\n| 1 - 5 | = 4;\nSum of these differences = 1 + 3 + 4 = 8;\nCreate an array to store this difference, let name it as \'ans\';\nso ans[] = [8];\n\nNow, index = 1, elem = 2;\n| 2 - 1 | = 1;\n| 2 - 4 | = 2;\n| 2 - 5 | = 3;\nSum of these differences = 1 + 2 + 3 = 6;\nso now ans[] = [8, 6];\n\nNow, index = 2, elem = 4;\n| 4 - 1 | = 3;\n| 4 - 2 | = 2;\n| 4 - 5 | = 1;\nSum of these differences = 3 + 2 + 1 = 6;\nso now ans[] = [8, 6, 6];\n\nNow, index = 3, elem = 5;\n| 5 - 1 | = 4;\n| 5 - 2 | = 3;\n| 5 - 4 | = 1;\nSum of these differences = 4 + 3 + 1 = 8;\nso the final ans[] = [8, 6, 6, 8];\n```\n\n# Can we formulate it?\nYes, of course. **But how?**\n\nLet\'s think of any random series (sorted or non sorted).\nx1 , x2, x3, x4, ... xn;\n\nIf we want to calculate the sum of difference between x3 and all other elements, what will we do?\n\nWe will just start taking the difference between x3 and other numbers and sum it, right!!\n\nBut what\'s behind the **scene**?\n\nActually we will be doing \n```\n(x3 - x1) + (x3 - x2) + (x3 - x4) + ... (x3 - xn)\n\n/* We can add (x3 - x3) as it will result 0,\nso it will not affect the result. */\n\n(x3 - x1) + (x3 - x2) + (x3 - x3) + (x3 - x4) + ... (x3 - xn)\n\nIt can be written like this ->\nn*x3 - (x1 + x2 + x3 + ... xn);\n\n```\nThis is not the answer, since we have to find the sum of absolute diff. Think of it\n\n```(x3 - x1) + (x3 - x2) + (x3 - x4) + ... (x3 - xn)``` \n\nif ```x3 > x1 && x3 > x2```\nbut ```x3 < x4 && x3 < x5 ... ```\n\n```(x3 - x1) and (x3 - x2)``` will give positive but ```(x3 - x4) and all the other elements after x3 will give negative value.\n\nAnd this is the **problem** i talked on the top.\n\nWe will keep track of the prefix sum in leftSum var which will store the sum of all the elements before the current element (Assume current element is x1);\n\nIn addition to prefix sum we need to keep track of the  postfix sum  in rightSum which will store the sum of all the elements after the curr element and the curr element.\n\nInitially ```leftSum = 0;``` and ```rightSum = x1 + x2 + x3 + ... xn;```\nIterate through the first element to last element.\n\n```\nabsDiff = ((number of elements before x1) * x1 - leftSum) +  (rightSum - (number of elements after x1 including x1) * x1);\n```\n\nLet\'s take the same example we took above\n```\nnums[] = [1,2,4,5];\n\nleftSum = 0;\nrightSum = 1 + 2 + 4 + 5 = 12;\n\nindex = 0, elem = 1;\nnumberOfElementBefore_1 = 0;\nnumberOfElementAfter_1_including_1 = 4;\n\nabsDiffFor_1 = (0*1 - leftSum) + (rightSum - 4*1) = (0 - 0) + (12 - 4) = 8;\n\n// store in ans array\nans[] = [8];\n\n// update leftSum and rightSum\nleftSum = leftSum + 1 = 1;\nrightSum = rightSum - 1 = 12 - 1 = 11;\n\nnums[] = [1,2,4,5];\nindex = 1, elem = 2;\nnumberOfElementBefore_2 = 1;\nnumberOfElementAfter_2_including_2 = 3;\n\nabsDiffFor_2 = (1*2 - leftSum) + (rightSum - 3*2) = (2 - 1) + (11 - 6) = 6;\n\n// store in ans array\nans[] = [8, 6];\n\n// update leftSum and rightSum\nleftSum = leftSum + 2 = 3;\nrightSum = rightSum - 2 = 11 - 2 = 9;\n\nnums[] = [1,2,4,5];\nindex = 2, elem = 4;\nnumberOfElementBefore_4 = 2;\nnumberOfElementAfter_4_including_4 = 2;\n\nabsDiffFor_4 = (2*4 - leftSum) + (rightSum - 2*4) = (8 - 3) + (9 - 8) = 6;\n\n// store in ans array\nans[] = [8, 6, 6];\n\n// update leftSum and rightSum\nleftSum = leftSum + 4 = 7;\nrightSum = rightSum - 4 = 9 - 4 = 5;\n\nnums[] = [1,2,4,5];\nindex = 3, elem = 5;\nnumberOfElementBefore_5 = 1;\nnumberOfElementAfter_5_including_5 = 1;\n\nabsDiffFor_5 = (3*5 - leftSum) + (rightSum - 1*5) = (15- 7) + (5 - 5) = 8;\n\n// store in ans array\nans[] = [8, 6, 6, 8];\n\n// update leftSum and rightSum\nleftSum = leftSum + 5 = 12;\nrightSum = rightSum - 4 = 5 - 5 = 0;\n```\n\nFinal ans ```ans[] = [8, 6, 6, 8];```\n\n\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {\n        int n = nums.size();\n        vector<int>ans;\n\n        int leftSum = 0, rightSum = 0;\n        for(int x:nums) rightSum += x;\n\n        for(int i=0; i<n; i++){\n            int absDiff = ((i*nums[i]) - leftSum) + (rightSum - (n-1-i+1)*nums[i]);\n            ans.push_back(absDiff);\n            leftSum += nums[i];\n            rightSum -= nums[i];\n        }\n\n        return ans;\n    }\n};\n```
['C++']