🚀 PrefixSum &  SuffixSum || Explained Intuition 🚀
Problem Description\n\nGiven a sorted integer array nums, create and return an array result of the same length, where each element result[i] represents the sum 
# Problem Description\n\nGiven a **sorted** integer array `nums`, create and return an array result of the same length, where each element `result[i]` represents the sum of absolute differences between `nums[i]` and all other elements in the array, **excluding** itself.\n\n- Constraints:\n    - `result[i] = |nums[0]-nums[i]| + |nums[1]-nums[i]| +......+ |nums[n]-nums[i]|` \n    - $2 <= nums.length <= 10^5$\n    - $1 <= nums[i] <= nums[i + 1] <= 10^4$\n\n\n---\n\n\n\n# Intuition\n\n\nHi there,\uD83D\uDE04\n\nLet\'s take a look\uD83D\uDC40 at our today\'s problem.\nWe have a **sorted** integer array and we are required to return an array such that for each element `i` in the **result** array, it equals the **absolute** **difference** of element `i` in original array and all other elements.\nIn other words, `result[i] = |nums[0]-nums[i]| + |nums[1]-nums[i]| +......+ |nums[n]-nums[i]|`\n\nSeem interesting problem.\uD83E\uDD29\n**First** thing that we can think of is our **big guy**\uD83D\uDCAA Brute Force, by looping with **nested loop** and for each element we compute the absolute difference between them and add it to our `result[i]`.\nFor us, this solution is inefficient since it takes $O(N^2)$ and will give us headace\uD83D\uDE02.\n\nHow can we improve this?\uD83E\uDD14\nSince for each element we want to compute the absolute difference between them and other elements in the array.\nWe can first thing **sum** all the elements of the array and for each element `i` we compute `|sum - nums[i] * size of arrray|` which means that we actually compute differece between each element and the current element.\nIt\'s code will be:\n```cpp\nvector<int> getSumAbsoluteDifferences(vector<int>& nums) {\n        int n = nums.size(), sum = 0;\n        vector<int> ans(n);\n        for(int i = 0 ; i < n ; i ++){\n            sum += nums[i] ;\n        }\n        for(int i = 0 ; i < n ; i ++){\n            int cur = abs(sum - nums[i] * n) ;\n            ans[i] = cur ;\n        }\n        return ans;\n    }\n```\nThis may look right from first look but unfortunately it is not valid answer.\uD83D\uDE14\n\nLet\'s see some examples to see why it is not valid:\n```\nnums = [2,3,5]\nsum = 10\nfor 2: |10 - 2 * 3| = |2 - 2 + 3 - 2 + 5 - 2| = |8 - 4| = 4\nfor 3: |10 - 3 * 3| = |2 - 3 + 3 - 3 + 5 - 3| = |7 - 6| = 1\nfor 5: |10 - 5 * 3| = |2 - 5 + 3 - 5 + 5 - 5| = |5 - 10| = 5\n```\n```\nnums = [1,4,6,8,10]\nsum = 29\nfor 1: |29 - 1 * 5| = |1 - 1 + 4 - 1 + 6 - 1 + 8 - 1 + 10 - 1| = |28 - 4| = 24\nfor 4: |29 - 4 * 5| = |1 - 4 + 4 - 4 + 6 - 4 + 8 - 4 + 10 - 4| = |25 - 16| = 9\n.\n.\n.\n```\n\nI think we got why it is wrong...\uD83D\uDE22\nWhat we are doing is\n`|nums[i] - nums[0] + nums[i] - nums[1] +..... nums[n] - nums[i]|` \nand this is far from our objective which is \n`|nums[0]-nums[i]| + |nums[1]-nums[i]| +......+ |nums[n]-nums[i]|`.\n\nNow we reached here, How can we get the right formula.\uD83E\uDD14\nWe can think about one thing.\nWhen is `|nums[i] - nums[0] + nums[i] - nums[1] +..... ` is equal to `|nums[0]-nums[i]| + |nums[1]-nums[i]| +......` ?\uD83E\uDD28\nI know that I said earlier that they are two different things but they can be equal in one case.... Actually two cases.\uD83E\uDD2F\n\nWhen `nums[i]` is greater than all other elements in the array so \n```\nnums[i]-nums[0] = |nums[0]-nums[i]|\nnums[i]-nums[1] = |nums[1]-nums[i]|\nnums[i]-nums[2] = |nums[2]-nums[i]|\n.\n.\nand so on so forth\n```\n\nand when `nums[i]` is smaller than all other elements in the array so \n```\nnums[0]-nums[i] = |nums[0]-nums[i]|\nnums[1]-nums[i] = |nums[1]-nums[i]|\nnums[2]-nums[i] = |nums[2]-nums[i]|\n.\n.\nand so on so forth\n```\n\nSince our array is already **sorted**, we can use these two cases to compute our objective so for each element we can use the **sum** trick two times -which was invalid first but now are valid-.\uD83E\uDD29\n\n**First time**, with all the elements **before** the current element since it is **greater** than them all and for this we can use **prefix** array to get immediately the sum of all elements **before** current element.\n\n**Second time**, with all the elements **after** the current element since it is **smaller** than them all and for this we can use **suffix** array to get immediately the sum of all elements **after** current element.\n\n\nAnd this is the solution for our today\'S problem I hope that you understood it\uD83D\uDE80\uD83D\uDE80\n\n\n\n\n---\n\n\n# Approach\n\n1. **Initialization:** Obtain the size of the input array `nums` and create a result array of the same size.\n    ```cpp\n    int n = nums.size();\n    vector<int> result(n);\n    ```\n2. **Prefix and Suffix Sums:** Create two additional arrays, `prefixSum` and `suffixSum`, to store the cumulative sums from the beginning and end of the `nums` array, respectively. Initialize the first element of both arrays -Don\'t forget that the input array is sorted- .\n    ```cpp\n    vector<int> prefixSum(n), suffixSum(n);\n    prefixSum[0] = nums[0];\n    suffixSum[n - 1] = nums[n - 1];\n    ```\n3. **Calculate Sums in One Loop:** Use a single loop to calculate both the prefix and suffix sums simultaneously.\n    ```cpp\n    for (int i = 1; i < n; ++i) {\n        prefixSum[i] = prefixSum[i - 1] + nums[i];\n        suffixSum[n - i - 1] = suffixSum[n - i] + nums[n - i - 1];\n    }\n    ```\n4. **Calculate Absolute Differences:** Iterate through the array and compute the absolute differences using the prefix and suffix sums.\n    ```cpp\n    for (int i = 0; i < n; ++i) {\n        int currentAbsoluteDiff = ((nums[i] * i) - prefixSum[i]) + (suffixSum[i] - (nums[i] * (n - i - 1)));\n        result[i] = currentAbsoluteDiff;\n    }\n    ```\n5. **Return** the calculated result array.\n\n## Complexity\n- **Time complexity:** $O(N)$\nSince we are **looping** over the input array **two** time, one time to calculate `prefix` and `suffix` arrays and another time to calculate the result which costs us `2 * N` so time complexity is `O(N)`.\nWhere `N` is the size of the input array.\n- **Space complexity:** $O(N)$\nSince are storing two arrays of the same length of the input array which are the prefix and suffix arrays which costs us `2 * N` so space complexity is `O(N)`.\n\n\n\n---\n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> result(n);\n        vector<int> prefixSum(n), suffixSum(n);\n        \n        // Calculate and initialize the prefix sums & suffixSum array\n        prefixSum[0] = nums[0];\n        suffixSum[n - 1] = nums[n - 1];\n        \n        // Calculate the prefix sums & suffixSum array in one loop\n        for (int i = 1; i < n; ++i) {\n            prefixSum[i] = prefixSum[i - 1] + nums[i];\n            suffixSum[n - i - 1] = suffixSum[n - i] + nums[n - i - 1];\n        }\n        \n        // Calculate absolute differences and update the result array\n        for (int i = 0; i < n; ++i) {\n            int currentAbsoluteDiff = ((nums[i] * i) - prefixSum[i]) + (suffixSum[i] - (nums[i] * (n - i - 1)));\n            result[i] = currentAbsoluteDiff;\n        }\n        \n        return result;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int[] getSumAbsoluteDifferences(int[] nums) {\n        int n = nums.length;\n        int[] result = new int[n];\n        int[] prefixSum = new int[n];\n        int[] suffixSum = new int[n];\n\n        // Calculate and initialize the prefix sums & suffixSum array\n        prefixSum[0] = nums[0];\n        suffixSum[n - 1] = nums[n - 1];\n\n        // Calculate the prefix sums & suffixSum array in one loop\n        for (int i = 1; i < n; ++i) {\n            prefixSum[i] = prefixSum[i - 1] + nums[i];\n            suffixSum[n - i - 1] = suffixSum[n - i] + nums[n - i - 1];\n        }\n\n        // Calculate absolute differences and update the result array\n        for (int i = 0; i < n; ++i) {\n            int currentAbsoluteDiff = ((nums[i] * i) - prefixSum[i]) + (suffixSum[i] - (nums[i] * (n - i - 1)));\n            result[i] = currentAbsoluteDiff;\n        }\n\n        return result;\n    }\n}\n```\n```Python []\nclass Solution:\n    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n        n = len(nums)\n        result = [0] * n\n        prefix_sum = [0] * n\n        suffix_sum = [0] * n\n\n        # Calculate and initialize the prefix sums & suffix_sum array\n        prefix_sum[0] = nums[0]\n        suffix_sum[n - 1] = nums[n - 1]\n\n        # Calculate the prefix sums & suffix_sum array in one loop\n        for i in range(1, n):\n            prefix_sum[i] = prefix_sum[i - 1] + nums[i]\n            suffix_sum[n - i - 1] = suffix_sum[n - i] + nums[n - i - 1]\n\n        # Calculate absolute differences and update the result array\n        for i in range(n):\n            current_absolute_diff = ((nums[i] * i) - prefix_sum[i]) + (suffix_sum[i] - (nums[i] * (n - i - 1)))\n            result[i] = current_absolute_diff\n\n        return result\n```\n```C []\nint* getSumAbsoluteDifferences(int* nums, int numsSize, int* returnSize) {\n    int* result = (int*)malloc(numsSize * sizeof(int));\n    *returnSize = numsSize;\n\n    int* prefixSum = (int*)malloc(numsSize * sizeof(int));\n    int* suffixSum = (int*)malloc(numsSize * sizeof(int));\n\n    // Calculate and initialize the prefix sums & suffixSum array\n    prefixSum[0] = nums[0];\n    suffixSum[numsSize - 1] = nums[numsSize - 1];\n\n    // Calculate the prefix sums & suffixSum array in one loop\n    for (int i = 1; i < numsSize; ++i) {\n        prefixSum[i] = prefixSum[i - 1] + nums[i];\n        suffixSum[numsSize - i - 1] = suffixSum[numsSize - i] + nums[numsSize - i - 1];\n    }\n\n    // Calculate absolute differences and update the result array\n    for (int i = 0; i < numsSize; ++i) {\n        int currentAbsoluteDiff = ((nums[i] * i) - prefixSum[i]) + (suffixSum[i] - (nums[i] * (numsSize - i - 1)));\n        result[i] = currentAbsoluteDiff;\n    }\n\n    // Free dynamically allocated memory\n    free(prefixSum);\n    free(suffixSum);\n\n    return result;\n}\n```\n\n\n![HelpfulJerry.jpg](https://assets.leetcode.com/users/images/f736826f-0d82-4480-952c-05d0a0ffb9c6_1700875279.2888722.jpeg)\n
['Array', 'Math', 'C', 'Prefix Sum', 'Python', 'C++', 'Java', 'Python3']