python dynamic programming using left and right sums
Intuition\nLet n = size of nums and m = size of queries. Brute force is O(n*m) but it is too slow to pass the tests. If we sort nums the problem is easier to gr
# Intuition\nLet n = size of nums and m = size of queries. Brute force is O(n*m) but it is too slow to pass the tests. If we sort nums the problem is easier to grasp. Now for any q in queries we know things bigger than q need to be reduced to q. So use binary search on the sorted nums to find how many such elements are there and the required # of operations.\n\n# Approach\nFollow intuition and precompute left and right sums. lsums[i] = sum of elements in nums[j] where j is < i. Similarly rsums[i] = sum of elements in nums[j] where j >= i\n\n# Complexity\n- Time complexity:\nn = size of nums\nm = size of queries\n\nnlog(n) to sort nums\nn to find lsums and rsums\nfor each query we do log(n) binary search nlog(n)\n\n= O (nlog(n) + mlog(n))\n\n- Space complexity:\nO(n + m)\n\n# Code\n```python3 []\nimport bisect\n\nclass Solution:\n    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n        n = len(nums)\n        m = len(queries)\n        lsums = [0 for i in range(n + 1)]\n        rsums = [0 for i in range(n + 1)]\n        s = sum(nums)\n        r = 0\n        nums = sorted(nums)\n        for i in range(n):\n            rsums[i] = s - r\n            lsums[i] = r\n            r += nums[i]\n        lsums[n] = s\n        rsums[n] = 0\n\n        ops = [0 for i in range(m)]\n        for j in range(m):\n            q = queries[j]\n            i = bisect.bisect_left(nums, q)\n            ops[j] = rsums[i] - (n - i) * q + i * q - lsums[i]\n        return ops\n\n```
['Python3']