✔C++|Prefix SUM | O(N)|O(1)|🔥
Intuition & Approach\n Describe your first thoughts on how to solve this problem. \nActually do a prefix sum and keep one equation in mind that is \nfor a parti
# Intuition & Approach\n<!-- Describe your first thoughts on how to solve this problem. -->\nActually do a prefix sum and keep one equation in mind that is \nfor a particular index we have `i` ways in which its positive and `n-i` ways in which its negative because our array is sorted we can draw this relation \n(nums[i] - nums[0]) + (nums[i] - nums[1]) + ... + (nums[i] - nums[i-1]) + (nums[i+1] - nums[i]) + (nums[i+2] - nums[i]) + ... + (nums[n-1] - nums[i]).\n- So we can see for a particular index `i` $$i*nums[i]$$ is positive and $$(n-i) *nusm[i]$$ elements are negative .\n- From above we can observe front ones are getting subtraced and back elemnts are being added so keep a prefix sum for both the sides\nAnd from this we can find a final relation with our answer:\n - $$res=abs(pref-(n-i)*arr[i]+(i)*arr[i]-diff)$$\n - keeping track with prefix sum of current index in both directions , from back side should be added and from front side should be subtracted  . You can dry run on some test cases for more clearity\n<!-- Describe your approach to solving the problem. -->\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\n# Code\n**Prefix Sum but Using extra space**\n```\nvector<int> getSumAbsoluteDifferences(vector<int>& arr) {\n        int n=arr.size();\n        vector<int>ans;\n        vector<int>pref(n,0),diff(n,0);\n        pref[n-1]=arr[n-1],diff[0]=0;\n        for(int i=1;i<n;i++){\n            pref[n-i-1]=pref[n-i]+arr[n-i-1];\n            diff[i]=diff[i-1]-arr[i-1];\n        }\n        \n        for(int i=0;i<n;i++){\n            int res=abs(pref[i]-(n-i)*arr[i]+(i)*arr[i]+diff[i]);\n            ans.push_back(res);\n        }\n        return ans;\n    }\n```\n**Optimized Prefix sum O(1) space**-->don\'t take ans as space we can do it in arr also\n```\nclass Solution {\npublic:\n    vector<int> getSumAbsoluteDifferences(vector<int>& arr) {\n        int n=arr.size();\n        vector<int>ans;\n        int pref=accumulate(arr.begin(),arr.end(),0),diff=0;\n        for(int i=0;i<n;i++){\n            int res=abs(pref-(n-i)*arr[i]+(i)*arr[i]-diff);\n            pref-=arr[i];\n            diff+=arr[i];\n            ans.push_back(res);\n        }\n        return ans;\n    }\n};\n```\n# If Help Full then Upvote \uD83D\uDD3C\uD83D\uDD3C\uD83D\uDD3C
['C++']