Illustrations for O(n) formula [Java, Kotlin, Python]
It is usually Hard to come up with a formula. For example:\n\nres[i] = sumTotal - (n - i - 1) * nums[i]  +  i * nums[i] - sumBelow\n\nTo infer the general formu
It is usually Hard to come up with a formula. For example:\n```\nres[i] = sumTotal - (n - i - 1) * nums[i]  +  i * nums[i] - sumBelow\n```\nTo infer the general formula, I like to use examples and plug real numbers.\n\n# **Tip on sum of absolute difference**\nReminder of `abs` function:\n\n## 1 Sum on the right side\n\n- (1) if `a > b` =>  `|a-b| = a - b > 0` , for n elements `n*|a-b| = n*(a-b)`\n- \nThe sum of differences  with this array below\n![image](https://assets.leetcode.com/users/images/b01230cc-1c36-42a3-8611-e20282a48767_1607889895.0969539.png)\n\nThe count of elements on the right is `n-i-1`\n`sumTotal` is sum of array elements minus the current element (index i)\n`n` is the array size.  \n\n```\nsum(|nums[i]-nums[j]|) =  |3-1| + |3-1| + |3-1| + |3-1|\n=  4 * |3-1| = 4 * 3 - 4 * 1 \n```\n\nFormula of sum of absolute differences on the right side\n```\nSumAbsoluteDifferencesRight = sumTotal - (n-i-1) * nums[i]\n```\n\n## 2 Sum on the left side\n- (2) if `b > a` =>  `|a-b| = b - a > 0`,  for n elements `n*|a-b| = n*(b-a)`\n\nThe current index `i` is on the other end.\n\n![image](https://assets.leetcode.com/users/images/5ce28620-7a45-4813-ba8f-67cf948315e3_1607890412.2249632.png)\n\nThe count of elements on the right is `i`\n`sumBelow` is the accumulated sum of array elements below the current element (index i)\n\n```\nsum(|nums[i]-nums[j]|) = |3-5| + |3-5| + |3-5| + |3-5|\n= 4 * |3-5| \n= 4 * (5-3)\n= 4*5 - 4*3\n```\n\nFormula of sum of absolute differences on the left side\n```\nSumAbsoluteDifferencesLeft = | sumBelow - (i) * nums[i] |\n=  i * nums[i] - sumBelow \n```\n# **O(n) computation**\n\nTo be linear, the trick is to calculate the sum of abs difference on left and right side  `res[i] = SumAbsoluteDifferencesRight + SumAbsoluteDifferencesLeft`\n\n![image](https://assets.leetcode.com/users/images/a8bbb4fd-2c61-41b7-a3ed-a5c2901f4c00_1607793557.2159398.png)\n\nThe current value at index i `nums[i]` is cancelled by its own difference.\nNow combine both and the general formula is\n\n```\nres[i] = SumAbsoluteDifferencesRight (1*) + SumAbsoluteDifferencesLeft (2*)\nres[i] = sumTotal - (n - i - 1) * nums[i]  +  i * nums[i] - sumBelow\n```\n\n## Solutions\nTime complexity: O(n)\nSpace complexity: O(n)\n\n**Java**\n\n```\nclass Solution {\n    public int[] getSumAbsoluteDifferences(int[] nums) {\n        int n = nums.length;\n        int[] res = new int[n];\n        int sumBelow = 0;\n        int sumTotal = Arrays.stream(nums).sum();\n\n        for (int i = 0; i < n; i++) {\n            int num = nums[i];\n            sumTotal -= num;\n            res[i] = sumTotal - (n - i - 1) * num + i * num - sumBelow;\n            sumBelow += num;\n        }\n        return res;\n    }\n}\n```\n\n**Kotlin**\n```\nclass Solution {\n    fun getSumAbsoluteDifferences(nums: IntArray): IntArray {\n        val n = nums.size\n        val res = IntArray(n)\n        var sumBelow = 0\n        var sumTotal = 0\n        for (num in nums) {\n            sumTotal += num\n        }\n        for (i in 0 until n) {\n            val num = nums[i]\n            sumTotal -= num\n            res[i] = sumTotal - (n - i - 1) * num + i * num - sumBelow\n            sumBelow += num\n        }\n        return res\n    }\n}\n```\n\n**Python**\n```\nclass Solution:\n    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n        n = len(nums)\n        sum_below = 0\n        sum_total = 0\n        for num in nums:\n            sum_total += num\n        \n        res = []\n        for i in range(n):\n            num = nums[i]\n            sum_total -= num\n            res.append(sum_total - (n - 1 - i) * num + i * num - sum_below)\n            sum_below += num\n        return res\n```\n\nSpecial thanks to \nhttps://leetcode.com/problems/sum-of-absolute-differences-in-a-sorted-array/discuss/969506/O(n)-python\nhttps://leetcode.com/problems/sum-of-absolute-differences-in-a-sorted-array/discuss/969525/C%2B%2B-O(n)-Track-Balance\n\n**Feel free to ask any question in the comment section.**
['Sliding Window', 'Python', 'Java', 'Kotlin']