【Video】Give me 10 minutes - How we think about a solution.
Intuition\nCalcuate left side and right side.\n\n---\n\n# Solution Video\n\nhttps://youtu.be/bwQh44GWME8\n\n\u25A0 Timeline of the video\n\n0:05 How we can solv
# Intuition\nCalcuate left side and right side.\n\n---\n\n# Solution Video\n\nhttps://youtu.be/bwQh44GWME8\n\n\u25A0 Timeline of the video\n\n`0:05` How we can solve this question\n`1:56` Calculate left total\n`6:32` Calculate right total\n`11:12` Create answers\n`11:51` Coding\n`14:14` Time Complexity and Space Complexity\n`14:39` Summary of the algorithm with my solution code\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 3,217\nMy first goal is 10,000 (It\'s far from done \uD83D\uDE05)\nThank you for your support!\n\n**My channel reached 3,000 subscribers these days. Thank you so much for your support!**\n\n---\n\n# Approach\n\n## How we think about a solution\n\nThis is brute force solution.\n```\nclass Solution:\n    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n        n = len(nums)\n        res = []\n\n        for i in range(n):\n            current_sum = 0\n\n            for j in range(n):\n                current_sum += abs(nums[i] - nums[j])\n\n            res.append(current_sum)\n\n        return res\n```\nBut I got `Time Limit Exceeded`. lol\n\nLook at Example 1.\n```\nInput: nums = [2,3,5]\n```\n```\nOutput: [4,3,5]\n\nresult[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,\nresult[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,\nresult[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.\n```\nLet\'s focus on this.\n```\n0 + 1 + 3 = 4\n1 + 0 + 2 = 3\n3 + 2 + 0 = 5\n```\nEach calculation has `0`. It means `current number` - `current number`. Look at positions for other numbers.\n```\n0 + 1 + 3 = 4\nWe have `1` and `3` on the right of `0`.\n\n1 + 0 + 2 = 3\nWe have `1` on the left of `0` and `2` on the right of `0`.\n\n3 + 2 + 0 = 5\nWe have `3` and `2` on the left of `0`.\n```\n\n---\n\n\u2B50\uFE0F Points\n\nWe should calculate left total and right total from 0 position, so that we will get the right answer.\n\n---\n\n- How we calculate both totals?\n\nLet\'s say we call left total `prefix` and right total `suffix`\n\n```\nInput: nums = [2,3,5]\n```\n\n```\nprefix_sum = 0\nsuffix_sum = 10 (= sum(nums))\n```\n### How to use prefix_sum\n`prefix_sum` is total of numbers we already met in the iteration.\n\nTo understand my idea easily, let me explain it when `index = 1`. In solution code, we start iteration from `index 0`. \n\nCalculate left side. When we move to `index 1`, `prefix_sum` should be `2`.\n```\ni: 1\nnum(= current number): 3\nprefix_sum = 2\n\nleft_sum = num * i - prefix_sum\n= 1 = 3 * 1 - 2\n```\n- Why `num * i - prefix_sum`?\n\nHow many numbers on the left of current number?\n\nThe answer is `1`. we only have `2` on the left side, so we need to multiply `current number` * `1`(= index) to calculate absolute value on the left side, because we need to subtract current number from each number on the left side.\n\n```\nnum * i = 3 * 1 = 3\n```\n`prefix_sum` is total of numbers we already met, which means total number of current left side. So if we subtract `prefix_sum` from `3`, we will get `left_sum`.\n```\nleft_sum = num * i - prefix_sum\n1 = 3 - 2\n```\nInput is \n```\n[2,3,5]\n   i\n\nWhen i = 1, abosulute value of left side is 1.\nresult[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,\n```\nLooks good.\n\nTo understand my idea easily, let me continue to calculate left side. In solution code, we calculate left side and right side in the same iteration.\n\n```\ni: 2\nnum(= current number): 5\nprefix_sum = 5 (= 2 + 3)\n\nleft_sum = num * i - prefix_sum\n= 5 = 5 * 2 - 5\n```\nAt `index 2`, we have two numbers(= `2` and `3`) on the left side of current index, so we need to subtract `5` from both numbers. That\'s why we need `5 * 2 = 10`.\n\nWe already met `2` and `3`, so current `prefix_sum` should be `5`. In the end,\n```\nleft_sum = 10 - 5\nresult[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.\n```\nLeft side is `5`(= `3 + 2`). Looks good.\n\nLet me calculate when i = 0\n\n```\ni: 0\nnum(= current number): 2\nprefix_sum = 0 (= no left number of current index)\n\nleft_sum = num * i - prefix_sum\n= 0 = 2 * 0 - 0\n\nresult[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,\n```\nLooks good!\n\n### How to use suffix_sum\nWe initialize `suffix_sum` like this.\n```\nsuffix_sum = 10 (= sum(nums))\n```\nWe use `suffix_sum` to caculate `right_sum` of current index. `suffix_sum` is total number of right side including current number.\n\nHow many numbers do we have on the right side?\n\nSimply, we subtract current index from total length of input array.\n```\n[2,3,5]\n i\ntotal length: 3\nwhen i = 0, number of right side is 3 - 0 = 3 (= 2,3,5)\n\n[2,3,5]\n   i\ntotal length: 3\nwhen i = 1, number of right side is 3 - 1 = 2 (= 3,5)\n\n[2,3,5]\n     i\ntotal length: 3\nwhen i = 2, number of right side is 3 - 2 = 1 (= 5)\n```\nWe apply the same idea of the left side. We will subtract current number * length of right side from `suffix_sum`.\n\n```\n[2,3,5]\ni = 0\nnum(= current number): 2\nsuffix_sum = 10 (= 2 + 3 + 5)\n\nright_sum = suffix_sum - num * (len(nums) - i)\n= 10 - 2 * (3 - 0)\n= 4\n\nresult[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4\n```\nRight side is `1 + 3 = 4` Looks good! We start from `index 0`, so every time we move to next index, total of right side should be smaller. On the other hand left side should be bigger.\n\n```\n[2,3,5]\ni = 1\nnum(= current number): 3\nsuffix_sum = 8 (= 3 + 5)\n\nright_sum = suffix_sum - num * (len(nums) - i)\n= 8 - 3 * (3 - 1)\n= 2\n\nresult[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,\n```\nRight side of `0` is `2`. Looks good!\n\n```\n[2,3,5]\ni = 2\nnum(= current number): 5\nsuffix_sum = 5 (= 5)\n\nright_sum = suffix_sum - num * (len(nums) - i)\n= 5 - 5 * (3 - 2)\n= 0\n\nresult[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.\n```\nRight side of `0` is `0`. Looks good!\n\nIn the end,\n\n```\ntotal_sum = left_sum + right_sum\n\nwhen index = 0\n4 = 0 + 4\nresult[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,\n\nwhen index = 1\n3 = 1 + 2\nresult[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,\n\nwhen index = 2\n5 = 5 + 0\nresult[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.\n\n```\n```\nOutput: [4,3,5]\n```\n\nEasy! \uD83D\uDE04\nLet\'s see a real algorithm!\n\n\n---\n\n\n### Algorithm Overview:\n\nIn each iteration, we calculate left sum and right sum and add both as a result.\n\n### Detailed Explanation:\n\n1. **Initialize an empty list to store the result:**\n   ```python\n   res = []\n   ```\n\n2. **Initialize variables for prefix and suffix sums:**\n   ```python\n   prefix_sum = 0\n   suffix_sum = sum(nums)\n   ```\n   - `prefix_sum`: This variable is used to keep track of the sum of elements to the left of the current element.\n   - `suffix_sum`: This variable is initialized as the sum of all elements in the array. It will be used to calculate the sum of elements to the right of the current element.\n\n3. **Iterate through each element in the array using `enumerate`:**\n   ```python\n   for i, num in enumerate(nums):\n   ```\n   - `i`: Represents the index of the current element.\n   - `num`: Represents the value of the current element.\n\n4. **Calculate the sum of elements to the left of the current element (`left_sum`):**\n   ```python\n   left_sum = num * i - prefix_sum\n   ```\n   - This calculates the sum of elements to the left of the current element by multiplying the value of the current element (`num`) with its index (`i`) and subtracting the running sum of elements encountered so far (`prefix_sum`).\n\n5. **Calculate the sum of elements to the right of the current element (`right_sum`):**\n   ```python\n   right_sum = suffix_sum - num * (len(nums) - i)\n   ```\n   - This calculates the sum of elements to the right of the current element by subtracting the running sum of elements (`suffix_sum`) from the product of the value of the current element (`num`) and the count of elements to its right (`len(nums) - i`).\n\n6. **Calculate the total sum of absolute differences for the current element (`total_sum`):**\n   ```python\n   total_sum = left_sum + right_sum\n   ```\n   - This combines the left and right sums to get the total sum of absolute differences for the current element.\n\n7. **Append the total sum to the result list (`res`):**\n   ```python\n   res.append(total_sum)\n   ```\n\n8. **Update the prefix sum and suffix sum for the next iteration:**\n   ```python\n   prefix_sum += num\n   suffix_sum -= num\n   ```\n   - `prefix_sum` is updated by adding the value of the current element (`num`).\n   - `suffix_sum` is updated by subtracting the value of the current element (`num`).\n\n9. **Return the final result list (`res`):**\n   ```python\n   return res\n   ```\n\nThis algorithm efficiently calculates the sum of absolute differences for each element in the array by taking advantage of the sorted nature of the array and updating prefix and suffix sums during each iteration.\n\n# Complexity\n- Time complexity: $$O(N)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\nExcept `res`.\n\n```python []\nclass Solution:\n    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n        # Initialize an empty list to store the result\n        res = []\n\n        # Initialize variables for prefix and suffix sums\n        prefix_sum = 0\n        suffix_sum = sum(nums)\n\n        # Iterate through each element in the array\n        for i, num in enumerate(nums):\n            # Calculate the sum of elements to the left of the current element\n            left_sum = num * i - prefix_sum\n\n            # Calculate the sum of elements to the right of the current element\n            right_sum = suffix_sum - num * (len(nums) - i)\n\n            # Calculate the total sum of absolute differences for the current element\n            total_sum = left_sum + right_sum\n\n            # Append the total sum to the result list\n            res.append(total_sum)\n\n            # Update the prefix sum and suffix sum for the next iteration\n            prefix_sum += num\n            suffix_sum -= num\n\n        # Return the final result list\n        return res        \n```\n```javascript []\nvar getSumAbsoluteDifferences = function(nums) {\n    let res = [];\n    let prefixSum = 0;\n    let suffixSum = nums.reduce((acc, num) => acc + num, 0);\n\n    for (let i = 0; i < nums.length; i++) {\n        let leftSum = nums[i] * i - prefixSum;\n        let rightSum = suffixSum - nums[i] * (nums.length - i);\n        let totalSum = leftSum + rightSum;\n\n        res.push(totalSum);\n\n        prefixSum += nums[i];\n        suffixSum -= nums[i];\n    }\n\n    return res;    \n};\n```\n```java []\nclass Solution {\n    public int[] getSumAbsoluteDifferences(int[] nums) {\n        int[] res = new int[nums.length];\n        int prefixSum = 0;\n        int suffixSum = 0;\n\n        for (int num : nums) {\n            suffixSum += num;\n        }\n\n        for (int i = 0; i < nums.length; i++) {\n            int leftSum = nums[i] * i - prefixSum;\n            int rightSum = suffixSum - nums[i] * (nums.length - i);\n            int totalSum = leftSum + rightSum;\n\n            res[i] = totalSum;\n\n            prefixSum += nums[i];\n            suffixSum -= nums[i];\n        }\n\n        return res;        \n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {\n        vector<int> res;\n        int prefixSum = 0;\n        int suffixSum = 0;\n\n        for (int num : nums) {\n            suffixSum += num;\n        }\n\n        for (int i = 0; i < nums.size(); i++) {\n            int leftSum = nums[i] * i - prefixSum;\n            int rightSum = suffixSum - nums[i] * (nums.size() - i);\n            int totalSum = leftSum + rightSum;\n\n            res.push_back(totalSum);\n\n            prefixSum += nums[i];\n            suffixSum -= nums[i];\n        }\n\n        return res;        \n    }\n};\n```\n\n---\n\nThank you for reading my post.\n\u2B50\uFE0F Please upvote it and don\'t forget to subscribe to my channel!\n\n\u25A0 Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n\u25A0 Twitter\nhttps://twitter.com/CodingNinjaAZ\n\n### My next daily coding challenge post and video.\n\npost\nhttps://leetcode.com/problems/largest-submatrix-with-rearrangements/solutions/4331142/video-give-me-10-minutes-how-we-think-about-a-solution/\n\nvideo\nhttps://youtu.be/odAv92zWKqs\n\n\u25A0 Timeline of the video\n\n`0:05` How we can move columns\n`1:09` Calculate height\n`2:48` Calculate width\n`4:10` Let\'s make sure it works\n`5:40` Demonstrate how it works\n`7:44` Coding\n`9:59` Time Complexity and Space Complexity\n`10:35` Summary of the algorithm with my solution code\n\n### My previous daily coding challenge post and video.\n\npost\nhttps://leetcode.com/problems/maximum-number-of-coins-you-can-get/solutions/4322538/video-give-me-4-minutes-how-we-think-about-a-solution/\n\nvideo\nhttps://youtu.be/HPzfCHfWPlY\n\n\u25A0 Timeline of the video\n`0:04` Two key points to solve this question\n`1:46` Demonstrate how it works\n`3:17` Coding\n`4:14` Time Complexity and Space Complexity\n`4:33` Summary of the algorithm with my solution code\n
['C++', 'Java', 'Python3', 'JavaScript']