<p>You are given two positive <strong>0-indexed</strong> integer arrays <code>nums1</code> and <code>nums2</code>, both of length <code>n</code>.</p>

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

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

<p>Return <em>the minimum <strong>sum of squared difference</strong> after modifying array </em><code>nums1</code><em> at most </em><code>k1</code><em> times and modifying array </em><code>nums2</code><em> at most </em><code>k2</code><em> times</em>.</p>

<p><strong>Note</strong>: You are allowed to modify the array elements to become <strong>negative</strong> integers.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1
<strong>Output:</strong> 43
<strong>Explanation:</strong> 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)<sup>2 </sup>+ (4 - 8)<sup>2 </sup>+ (10 - 7)<sup>2 </sup>+ (12 - 9)<sup>2</sup>&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.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums1.length == nums2.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums1[i], nums2[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= k1, k2 &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def minSumSquareDiff(self, nums1: List[int], nums2: List[int], k1: int, k2: int) -> int:
        # create a max heap by taking the negative of the absolute differences
        heap = [-abs(x - y) for x, y in zip(nums1, nums2)]
        # calculate the total sum of the differences (since we took negatives, sum is also negative)
        s = -sum(heap)
        # if we have enough modification chances to reduce all differences to 0, return 0
        if k1 + k2 >= s:
            return 0
        # total available modifications (k1 + k2)
        delta = k1 + k2
        # convert the list into a heap in-place (min-heap, but acts as max-heap due to negative values)
        heapify(heap)
        # number of elements in nums1 (or nums2, since they are of equal length)
        n = len(nums1)
        # while we still have modification chances left
        while delta > 0:
            # extract the largest difference (convert it back to positive by negating)
            d = -heappop(heap)
            # calculate the maximum possible reduction for the largest difference
            # gap is the minimum between delta // n (distributed reductions) and 1, unless heap is empty
            gap = max(delta // n, 1) if heap else delta
            # reduce the largest difference by 'gap'
            d -= gap
            # push the reduced difference back into the heap (negated to maintain max-heap behavior)
            heappush(heap, -d)
            # subtract the used reduction amount from the total available modifications
            delta -= gap
        # calculate the sum of squared differences (convert back to positive while summing)
        return sum(pow(e, 2) for e in heap)



        # Approach 2: keep track of the largest number and its count
        # combine the number of allowed modifications from both k1 and k2
        k = k1 + k2
        # calculate the absolute differences between nums1 and nums2
        # exclude pairs where the difference is zero
        nums = [abs(num1 - num2) for num1, num2 in zip(nums1, nums2) if num1 - num2 != 0]
        # add a zero to the list to handle the final reduction case uniformly
        nums.append(0)
        # sort the differences in descending order
        nums.sort(reverse=True)
        # initialize the largest number (leftNum) and its count (leftCnt)
        leftNum, leftCnt = nums[0], 1
        # iterate through the sorted differences
        for i in range(1, len(nums)):
            # calculate the total difference that can be reduced with the current leftCnt
            d = (leftNum - nums[i]) * leftCnt
            if d <= k:
                # if we can reduce all occurrences of the current max difference to the next level
                k -= d  # subtract the used modifications
                leftNum, leftCnt = nums[i], leftCnt + 1  # update leftNum and increase leftCnt
            else:
                # if not enough modifications to reduce all occurrences to the next level
                leftNum -= k // leftCnt  # evenly distribute the remaining modifications
                r = k % leftCnt  # calculate the remainder of modifications
                # calculate the final sum of squared differences
                return leftNum**2 * (leftCnt - r) + (leftNum - 1)**2 * r + \
                       sum(num**2 for num in nums[i:])
        # if all differences are reduced to zero, return 0
        return 0



        # # Approach 3: TLE, pass 30/38
        # n = len(nums1)
        # # calculate the absolute differences between nums1 and nums2
        # diff = [abs(nums1[i] - nums2[i]) for i in range(n)]
        # # total number of modifications allowed
        # modifyChances = k1 + k2
        # # if we have enough modifications to reduce all differences to zero, return 0
        # if modifyChances >= sum(diff):
        #     return 0
        # # sort the differences in descending order
        # diff.sort(reverse=True)
        # # iterate through the sorted differences
        # for i in range(n):
        #     # find the next lower value in the list (or 0 if at the end of the list)
        #     nextValue = diff[i+1] if i < n-1 else 0
        #     # calculate the maximum possible reduction for the current segment
        #     maxReduce = diff[i] - nextValue
        #     maxReduceCount = (i + 1)  # number of elements with the current max value
        #     # total reduction possible by reducing all current max elements to the next value
        #     totalReduce = maxReduce * maxReduceCount
        #     if modifyChances >= totalReduce:
        #         # reduce all elements in the current segment to the next lower value
        #         for j in range(i + 1):
        #             diff[j] -= maxReduce
        #         # subtract the used modifications
        #         modifyChances -= totalReduce
        #     else:
        #         # evenly distribute the remaining reductions
        #         fullReduce = modifyChances // maxReduceCount
        #         remainderReduce = modifyChances % maxReduceCount
        #         # apply full reduction to each element in the current segment
        #         for j in range(i + 1):
        #             diff[j] -= fullReduce
        #         # apply the remainder reductions one by one
        #         for j in range(remainderReduce):
        #             diff[j] -= 1
        #         # no more modifications available
        #         modifyChances = 0
        #         break
        # # calculate the sum of squared differences
        # output = sum(x * x for x in diff)
        # return output
1466