You are given two positive 0-indexed integer arrays nums1 and nums2, both of length n.

The sum of squared difference of arrays nums1 and nums2 is defined as the sum of (nums1[i] - nums2[i])2 for each 0 &lt;= i &lt; n.

You are also given two positive integers k1 and k2. You can modify any of the elements of nums1 by +1 or -1 at most k1 times. Similarly, you can modify any of the elements of nums2 by +1 or -1 at most k2 times.

Return the minimum sum of squared difference after modifying array nums1 at most k1 times and modifying array nums2 at most k2 times.

Note: You are allowed to modify the array elements to become negative integers.

&nbsp;
Example 1:

Input: nums1 = [1,2,3,4], nums2 = [2,10,20,19], k1 = 0, k2 = 0
Output: 579
Explanation: The elements in nums1 and nums2 cannot be modified because k1 = 0 and k2 = 0. 
The sum of square difference will be: (1 - 2)2 + (2 - 10)2 + (3 - 20)2 + (4 - 19)2&nbsp;= 579.


Example 2:

Input: nums1 = [1,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1
Output: 43
Explanation: One way to obtain the minimum sum of square difference is: 
- Increase nums1[0] once.
- Increase nums2[2] once.
The minimum of the sum of square difference will be: 
(2 - 5)2 + (4 - 8)2 + (10 - 7)2 + (12 - 9)2&nbsp;= 43.
Note that, there are other ways to obtain the minimum of the sum of square difference, but there is no way to obtain a sum smaller than 43.

&nbsp;
Constraints:


	n == nums1.length == nums2.length
	1 &lt;= n &lt;= 105
	0 &lt;= nums1[i], nums2[i] &lt;= 105
	0 &lt;= k1, k2 &lt;= 109


class Solution:
    def minSumSquareDiff(self, nums1: List[int], nums2: List[int], k1: int, k2: int) -> int:
        n = len(nums1)
        k = k1+k2 # can combine k's because items can be turned negative
        diffs = sorted((abs(x - y) for x, y in zip(nums1, nums2)))
        
        # First binary search to find our new max for our diffs array
        l, r = 0, max(diffs)
        while l < r:
            mid = (l+r)//2
            
            # steps needed to reduce all nums greater than newMax
            steps = sum(max(0, num-mid) for num in diffs)
            
            if steps <= k:
                r = mid
            else:
                l = mid+1
                
        newMax = l
        k -= sum(max(0, num-newMax) for num in diffs) # remove used k

        # Second binary search to find first index to replace with max val
        l, r = 0, n-1
        while l < r:
            mid = (l+r)//2
            if diffs[mid] < newMax:
                l = mid+1
            else:
                r = mid

        # Replace items at index >= l with newMax
        diffs = diffs[:l]+[newMax]*(n-l)
        
        # Use remaining steps to reduce overall score
        for i in range(len(diffs)-1,-1,-1):
            if k == 0 or diffs[i] == 0: break
            diffs[i] -= 1
            k -= 1
            
        return sum(diff*diff for diff in diffs)
class Solution {
    /** Algorithm
        1. Count the differences between each nums1[i] and nums2[i] and store them into an int[100_001], as nums is between 0 and 100_000.
        2. Let's look at the example of [1,4,10,12], [4,8,6,7]. k1= 1, k2 =1
             Looking at the pairs of abs diff we have 3,4,4,5.
             So a total of 16 diff points with k = 2.
             As we observe, if we use the k operations on the first pair, we can decrease 3 to 1.
             but this would only help with 3^2 (9) -> 1. So we decrease the totam sum diff by 8.
             However, if we operate on the diff of 5, this would have much more impact.
             5 - 1 => (4^2)25 - 16 . so we save 9 points by using 1 k
             5 - 2 => (3^2) 25 - 9. So we save 16 points.
         3. As we can see, we need to operate on the highest diff, lowering them.
         4. As we have counted them on step #1, we would have an array like this
           [0,0,0,1,2,1] : 1 diff of 3, 2 of 4 and 1 of 5.
         5. While k is > 0 (k1 + k2), start from the back (highest) and decrease it one group at a time.
           So make all 5 diffs into 4 diff, only if their cardinal is <= k. If it's greater than k, we can only
           lower k diff to diff -1.
           So [0,0,0,1,2,1] and k = 2 => [0,0,0,1,3,0] and k =1
           We have 3 diff of 4 and just k =1 so we can turn one 4 into a 3.
           => [0,0,0,2,2,0]. Thus. the diff becomes 2 of 3 and 2 of 4.
    */
    public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {
        long minSumSquare = 0;
        int[] diffs = new int[100_001];
        long totalDiff = 0;
        long kSum = k1 + k2;
        int currentDiff;
        int maxDiff = 0;
        for (int i = 0; i < nums1.length; i++) {
            // get current diff.
            currentDiff = Math.abs(nums1[i] - nums2[i]);
            // if current diff > 0, count/store it. If not,then ignore it.
            if (currentDiff > 0) {
                totalDiff += currentDiff;
                diffs[currentDiff]++;
                maxDiff = Math.max(maxDiff, currentDiff);
            }
        }
        // if kSum (k1 + k2) < totalDifferences, it means we can make all numbers/differences 0s
        if (totalDiff <= kSum) {
            return 0;
        }
        // starting from the back, from the highest difference, lower that group one by one to the previous group.
         // we need to make all n diffs to n-1, then n-2, as long as kSum allows it.
        for (int i = maxDiff; i> 0 && kSum > 0; i--) {
            if (diffs[i] > 0) {
                // if current group has more differences than the totalK, we can only move k of them to the lower level.
                if (diffs[i] >= kSum) {
                    diffs[i] -= kSum;
                    diffs[i-1] += kSum;
                    kSum = 0;
                } else {
                    // else, we can make this whole group one level lower.
                    diffs[i-1] += diffs[i];
                    kSum -= diffs[i];
                    diffs[i] = 0;
                }
            }
        }

        for (int i = 0; i <= maxDiff; i++) {
            if (diffs[i] > 0) {
                minSumSquare += (long) (Math.pow((long)i, 2)) * diffs[i];
            }
        }
        return minSumSquare;
    }
}
class Solution {
public:
    long long minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2) {
        int n = nums1.size();
        vector<int> diff(n);
        for(int i = 0; i<n; ++i) {
            diff[i] = abs(nums1[i] - nums2[i]);
        }
        int M = *max_element(diff.begin(), diff.end());
        vector<int> bucket(M+1);
        for(int i = 0 ; i<n; ++i) {
            bucket[diff[i]]++;
        }
        int k = k1 + k2;
        for(int i = M; i > 0; --i) {
            if(bucket[i] > 0) {
                int minus = min(bucket[i], k);
                bucket[i] -= minus;
                bucket[i-1] += minus;
                k -= minus;
            }
        }
        long long ans = 0;
        for(long long i = M; i > 0; --i) {
            ans += bucket[i]*i*i;
        }
        return ans;
    }
};
var minSumSquareDiff = function(nums1, nums2, k1, k2) {
    const len = nums1.length;
    const diff = new Array(len).fill(0);
    for(let i = 0; i < len; i++) {
        diff[i] = Math.abs(nums1[i] - nums2[i]);
    }
    diff.sort((a, b) => b - a);
    const bucket = new Array(diff[0] + 1).fill(0);
    let tk = k1 + k2;
    for(let i of diff) {
        bucket[i]++;
    }
    for(let i = bucket.length - 1; tk > 0 && i >= 0; i--) {
        if(bucket[i] == 0) continue; 
        const reduce = Math.min(bucket[i], tk);
        bucket[i] -= reduce;
        bucket[i-1] += reduce;
        tk -= reduce;
    }
    let ans = 0;
    for(let i = bucket.length - 1; i >= 1; i--) {
        ans += bucket[i] * i * i;
    }
    return ans;
};
Minimum Sum of Squared Difference