Prefix Sum + Binary Search | Detailed Explanation | Python3
Intuition\nWe have to equalize left and right sums based on where the desired value of all elements should be. This equalization point is a dividing index which
# Intuition\nWe have to equalize left and right sums based on where the desired value of all elements should be. This equalization point is a dividing index which can be rapidly found if the nums list is pre-sorted, using binary search. The accumulated sums (prefix sum) can be stored for all queries so it does not have to be re-computed. The tricky parts are the edge cases which are not so hard when you think it through.\n\n# Approach\nSo, pre-sort the list using Python3 List sort() method (timsort O(n log n)). Use itertools.accumulate to create a prefix sum. We want to 0 pad this (add a 0 at the start) so we don\'t have to offset the bisect indexes. Bisect right is what we want. When we are equalizing to a value that already exists, the index which is returned points just past the end of the value. With the 0-padding, this becomes the index of the prefix sum which includes the last value which is <= the desired. The edge case with bisect is that it points to len(arr). When this happens, we would get out of bounds, so need to test if that is the case and offset it by -1. At that point it would correspond to the left sum equaling again the last value which is <= the desired. It is trivial to then get the right sum, which is just the last element of the prefix array (equal to the sum of the entire array) subtracted by the left sum. Then, avoid dealing with floats (if you divided the left / right sums by the number of their elements) by just multiplying the number of elements in the left / right sections of the array by the desired value. By then subtracting from this the current sums of the left / right sections, you get the number of increment / decrement operations you need to equalize the entire array.\n\nThen just do this for each q in queries, append to a ret list, and return that list at the end.\n\n# Complexity\n- Time complexity:\n$$O(n\\ log\\ n)$$ - for time growth relative to the size of the array, Python\'s built in timsort and bisect binary search for each q in queries are of equal complexity (linearithmic)\n\n- Space complexity:\n$$O(n)$$ - for prefix array\n\n# Code\n```\nclass Solution:\n    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n        nums.sort()\n        n = len(nums)\n        prefix = [0] + list(itertools.accumulate(nums))\n        ret = []\n        for q in queries:\n            dividingIndex = bisect.bisect_right(nums, q)\n\n            if dividingIndex == n:\n                dividingIndex -= 1\n\n            leftSum = prefix[dividingIndex]\n            leftNumberElem = dividingIndex\n\n            rightSum = prefix[-1] - leftSum\n            rightNumberElem = n - dividingIndex\n\n            leftDelta = abs(leftNumberElem * q - leftSum)\n            rightDelta = abs(rightNumberElem * q - rightSum)\n\n            ret.append(leftDelta + rightDelta)\n        return ret\n```
['Python3']