# Minimum Sum of Squared Difference
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-sum-of-squared-difference)
Canonical: https://scaleengineer.com/dsa/problems/minimum-sum-of-squared-difference
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
---
## Problem
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 <= i < 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.

**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 = 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 = 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.

**Constraints:**

* `n == nums1.length == nums2.length`
* `1 <= n <= 105`
* `0 <= nums1[i], nums2[i] <= 105`
* `0 <= k1, k2 <= 109`

# Approaches
## Greedy Simulation with Max Heap
This approach uses a greedy strategy. The core idea is that to achieve the maximum reduction in the sum of squared differences, we should always decrease the largest current difference. A max heap (Priority Queue in Java) is a natural data structure to efficiently retrieve the largest difference at each step. We simulate the process by repeatedly taking the largest difference, reducing it by one, and putting it back, for a total of `k` times.
**Time:** O(n + k * log n). Building the heap takes O(n). The main loop runs `k` times, and each heap operation (poll/add) takes O(log n). Since `k` can be up to `2 * 10^9`, this will be too slow. · **Space:** O(n) to store up to `n` differences in the priority queue.
**Pros:** Simple to understand and implement the greedy logic directly.; Correct for all cases, but not always efficient.
**Cons:** Inefficient for large values of `k`, as the main loop runs `k` times, leading to a Time Limit Exceeded (TLE) verdict on platforms with strict time limits.
### Explanation
The problem can be simplified by observing that an operation on `nums1` or `nums2` has an equivalent effect on the absolute difference `|nums1[i] - nums2[i]|`. Thus, we can combine `k1` and `k2` into a single pool of `k = k1 + k2` operations, each of which can decrease a difference by 1.

The greedy choice is to always reduce the largest existing difference, as this yields the greatest decrease in the sum of squares. For a difference `d`, changing it to `d-1` reduces the sum of squares by `d^2 - (d-1)^2 = 2d - 1`, which is maximized when `d` is maximized.

This leads to a simulation-based approach:
1.  First, calculate all initial absolute differences and store the non-zero ones in a max heap.
2.  Also, compute the total sum of differences. If this sum is less than or equal to `k`, we can make all differences zero, so the answer is 0.
3.  Otherwise, we loop `k` times. In each iteration, we extract the largest difference from the heap, decrement it, and re-insert it if it's still greater than zero.
4.  Finally, after exhausting all `k` operations, we compute the sum of squares of the differences remaining in the heap.

```java
import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
    public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {
        int n = nums1.length;
        long k = k1 + k2;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        long totalDiff = 0;

        for (int i = 0; i < n; i++) {
            int diff = Math.abs(nums1[i] - nums2[i]);
            if (diff > 0) {
                maxHeap.add(diff);
            }
            totalDiff += diff;
        }

        if (totalDiff <= k) {
            return 0;
        }

        while (k > 0 && !maxHeap.isEmpty()) {
            int maxDiff = maxHeap.poll();
            maxDiff--;
            if (maxDiff > 0) {
                maxHeap.add(maxDiff);
            }
            k--;
        }

        long sumOfSquares = 0;
        while (!maxHeap.isEmpty()) {
            long val = maxHeap.poll();
            sumOfSquares += val * val;
        }
        return sumOfSquares;
    }
}
```
### Algorithm
- Combine the available operations: `k = k1 + k2`.
- Calculate the absolute difference `d[i] = |nums1[i] - nums2[i]|` for each pair of elements.
- Insert all non-zero differences into a max heap (Priority Queue).
- If the total sum of differences is already less than or equal to `k`, it means we can make all differences zero. The result is 0.
- Perform `k` operations: In a loop that runs `k` times, extract the maximum element `d` from the heap, decrease it by one, and insert `d-1` back into the heap if it's still positive.
- After the loop, the heap contains the final values of the differences.
- Calculate the sum of squares of all elements remaining in the heap.

## Binary Search on the Answer
Instead of simulating the reduction one by one, we can determine the final state of the differences more efficiently. The greedy strategy implies that after all operations, the differences will be "leveled off". All differences will be at most some value `T`, with some possibly at `T` and others at `T-1`. We can use binary search to find the smallest possible value for this threshold `T`. For a given candidate threshold `mid`, we can quickly calculate if it's achievable with `k` operations. This allows us to narrow down the search space for the optimal threshold efficiently.
**Time:** O(n * log(D)), where `D` is the maximum possible initial difference (e.g., 10^5). The binary search runs `log(D)` times, and inside it, we iterate through `n` differences. This is efficient enough for the given constraints. · **Space:** O(n) to store the array of differences. This can be optimized to O(1) if we re-calculate differences inside the check function, but at the cost of slightly higher runtime.
**Pros:** Much more efficient than the simulation approach for large `k`.; Avoids the TLE issue by not depending on `k` for the loop count.
**Cons:** More complex to reason about and implement correctly compared to the direct simulation.; Slightly less efficient than the frequency counting approach for the given constraints.
### Explanation
This approach hinges on finding the final state without simulating each step. The greedy strategy ensures that we'll end up with a set of differences where the maximum value is minimized. We can binary search for this final maximum value.

1.  **Binary Search:** We search for a `target` difference in the range `[0, max_diff]`. For a chosen `mid`, we check if it's possible to make all differences `<= mid`.
2.  **Check Function:** To do this, we calculate the operations needed: `ops_needed = sum(d - mid)` for all differences `d > mid`. If `ops_needed <= k`, then `mid` is achievable, and we can try for an even smaller target. Otherwise, `mid` is too ambitious, and we need to aim higher.
3.  **Final Calculation:** Once the binary search finds the smallest possible `target`, we know that all original differences `d > target` will be reduced to `target`. We calculate the operations spent on this, `k_used`. The remaining operations, `k_rem = k - k_used`, are then used to reduce `k_rem` of the `target`-level differences to `target - 1`.
4.  The final sum of squares is calculated from this final distribution of differences.

```java
class Solution {
    public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {
        int n = nums1.length;
        long k = k1 + k2;
        int[] diffs = new int[n];
        long totalDiff = 0;
        int maxDiff = 0;

        for (int i = 0; i < n; i++) {
            diffs[i] = Math.abs(nums1[i] - nums2[i]);
            totalDiff += diffs[i];
            maxDiff = Math.max(maxDiff, diffs[i]);
        }

        if (totalDiff <= k) {
            return 0;
        }

        // Binary search for the target difference
        int low = 0, high = maxDiff;
        int target = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            long opsNeeded = 0;
            for (int d : diffs) {
                if (d > mid) {
                    opsNeeded += (d - mid);
                }
            }
            if (opsNeeded <= k) {
                target = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        // Calculate remaining k and final sum
        long remainingK = k;
        for (int i = 0; i < n; i++) {
            if (diffs[i] > target) {
                remainingK -= (diffs[i] - target);
                diffs[i] = target;
            }
        }

        // Distribute remaining k to reduce target to target-1
        for (int i = 0; i < n && remainingK > 0; i++) {
            if (diffs[i] == target) {
                diffs[i]--;
                remainingK--;
            }
        }

        long sumOfSquares = 0;
        for (int d : diffs) {
            sumOfSquares += (long)d * d;
        }
        return sumOfSquares;
    }
}
```
### Algorithm
- Calculate the initial absolute differences `d[i] = |nums1[i] - nums2[i]|`. Let `k = k1 + k2`.
- If the total sum of differences is `<= k`, return 0.
- Binary search for the optimal final maximum difference, let's call it `target`, in the range `[0, max_initial_diff]`.
- For a given `mid` value in the binary search, define a `check(mid)` function. This function calculates the total operations needed to make every difference `d[i]` at most `mid`. This is `sum(d[i] - mid)` for all `d[i] > mid`.
- If `check(mid) <= k`, it means `mid` is a possible maximum difference. We try for a smaller one by setting `high = mid - 1`.
- If `check(mid) > k`, `mid` is too small, we need to allow a larger maximum difference, so we set `low = mid + 1`.
- The binary search will find the smallest threshold `T` such that we can make all differences at most `T`.
- After finding `T`, calculate the operations used to reduce all differences greater than `T` down to `T`. Let the remaining operations be `k_rem`.
- The final differences will be: `d[i]` if `d[i] < T`, and `T` if `d[i] >= T`. We use the `k_rem` operations to reduce `k_rem` of the differences that are now `T` down to `T-1`.
- Calculate the final sum of squares based on this new distribution of differences.

## Greedy with Frequency Counting
This is an optimization of the greedy approach. Instead of processing one difference at a time with a heap, we can process all differences of the same value in a single step. We use a frequency map (or an array, since differences are bounded) to store the counts of each difference value. We then iterate from the largest difference downwards, reducing them in batches. This avoids the logarithmic overhead of a heap and the repeated passes of binary search, making it the most efficient method.
**Time:** O(n + D), where `D` is the maximum possible initial difference. O(n) to compute differences and build the frequency map, and O(D) to iterate through the frequencies. This is linear and highly efficient. · **Space:** O(D), where `D` is the maximum possible initial difference (10^5), for the frequency array.
**Pros:** Most efficient time complexity among the three approaches.; Conceptually builds on the greedy idea but processes items in batches for superior performance.
**Cons:** Requires extra space for the frequency map, which depends on the range of differences, not just the input size `n`.
### Explanation
This approach refines the greedy strategy by processing elements in batches. Instead of a priority queue, we use a frequency array to count occurrences of each difference value. The maximum possible difference is bounded (10^5), making an array feasible.

1.  **Frequency Mapping:** We first compute all absolute differences and populate a frequency array, `freq`, where `freq[d]` holds the number of pairs with difference `d`.
2.  **Greedy Batch Reduction:** We iterate downwards from the maximum difference `d = max_diff` to 1. At each step `d`, we look at `count = freq[d]`. These are the largest current differences.
    - If we have enough operations (`k >= count`), we can reduce all of them from `d` to `d-1`. We update `k` by subtracting `count` and transfer the count from `freq[d]` to `freq[d-1]`.
    - If `k < count`, we only have enough operations to reduce `k` of them. We update `freq[d]` and `freq[d-1]` accordingly, set `k` to 0, and stop, as we can't perform any more reductions.
3.  **Final Summation:** After the loop finishes (either by running out of operations or checking all differences), the `freq` array holds the final counts of each difference value. The minimum sum of squared differences is the sum of `d*d*freq[d]` over all `d`.

```java
class Solution {
    public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {
        long k = k1 + k2;
        int n = nums1.length;
        int maxDiff = 0;
        long totalDiff = 0;
        
        // Using an array as a frequency map since diff is bounded
        int[] freq = new int[100001]; 
        for (int i = 0; i < n; i++) {
            int diff = Math.abs(nums1[i] - nums2[i]);
            freq[diff]++;
            maxDiff = Math.max(maxDiff, diff);
            totalDiff += diff;
        }

        if (totalDiff <= k) {
            return 0;
        }

        for (int d = maxDiff; d > 0; d--) {
            if (freq[d] == 0) {
                continue;
            }
            
            long count = freq[d];
            if (k >= count) {
                // Reduce all 'd' differences to 'd-1'
                k -= count;
                freq[d-1] += count;
                freq[d] = 0;
            } else {
                // Reduce 'k' of the 'd' differences to 'd-1'
                freq[d-1] += k;
                freq[d] -= k;
                k = 0;
                break; // No more operations left
            }
        }

        long sumOfSquares = 0;
        for (long d = 1; d <= maxDiff; d++) {
            if (freq[(int)d] > 0) {
                sumOfSquares += freq[(int)d] * d * d;
            }
        }
        return sumOfSquares;
    }
}
```
### Algorithm
- Combine operations: `k = k1 + k2`.
- Calculate absolute differences `d[i] = |nums1[i] - nums2[i]|`.
- Create a frequency array `freq` of size `max_diff + 1`, where `freq[d]` stores the number of times difference `d` occurs.
- If the total sum of differences is `<= k`, return 0.
- Iterate from `d = max_diff` down to 1.
- At each difference `d`, we have `freq[d]` elements with this value.
- If we have enough operations `k` to reduce all `freq[d]` elements from `d` to `d-1` (i.e., `k >= freq[d]`):
    - Use `freq[d]` operations: `k -= freq[d]`.
    - Move the counts: `freq[d-1] += freq[d]`, `freq[d] = 0`.
- If `k < freq[d]`:
    - We can only reduce `k` of these elements.
    - Update counts: `freq[d-1] += k`, `freq[d] -= k`.
    - Set `k = 0` and break the loop, as no more operations are left.
- After the loop, the `freq` array represents the final distribution of differences.
- Calculate the sum of squares: `sum(d^2 * freq[d])` for all `d > 0`.

# Solutions
### Java

```java
class Solution { public long minSumSquareDiff ( int [] nums1 , int [] nums2 , int k1 , int k2 ) { int n = nums1 . length ; int [] d = new int [ n ]; long s = 0 ; int mx = 0 ; int k = k1 + k2 ; for ( int i = 0 ; i < n ; ++ i ) { d [ i ] = Math . abs ( nums1 [ i ] - nums2 [ i ]); s += d [ i ]; mx = Math . max ( mx , d [ i ]); } if ( s <= k ) { return 0 ; } int left = 0 , right = mx ; while ( left < right ) { int mid = ( left + right ) >> 1 ; long t = 0 ; for ( int v : d ) { t += Math . max ( v - mid , 0 ); } if ( t <= k ) { right = mid ; } else { left = mid + 1 ; } } for ( int i = 0 ; i < n ; ++ i ) { k -= Math . max ( 0 , d [ i ] - left ); d [ i ] = Math . min ( d [ i ], left ); } for ( int i = 0 ; i < n && k > 0 ; ++ i ) { if ( d [ i ] == left ) { -- k ; -- d [ i ]; } } long ans = 0 ; for ( int v : d ) { ans += ( long ) v * v ; } return ans ; } }
```

### CPP

```cpp
using ll = long long ; class Solution { public: long long minSumSquareDiff ( vector < int >& nums1 , vector < int >& nums2 , int k1 , int k2 ) { int n = nums1 . size (); vector < int > d ( n ); ll s = 0 ; int mx = 0 ; int k = k1 + k2 ; for ( int i = 0 ; i < n ; ++ i ) { d [ i ] = abs ( nums1 [ i ] - nums2 [ i ]); s += d [ i ]; mx = max ( mx , d [ i ]); } if ( s <= k ) return 0 ; int left = 0 , right = mx ; while ( left < right ) { int mid = ( left + right ) >> 1 ; ll t = 0 ; for ( int v : d ) t += max ( v - mid , 0 ); if ( t <= k ) right = mid ; else left = mid + 1 ; } for ( int i = 0 ; i < n ; ++ i ) { k -= max ( 0 , d [ i ] - left ); d [ i ] = min ( d [ i ], left ); } for ( int i = 0 ; i < n && k ; ++ i ) { if ( d [ i ] == left ) { -- k ; -- d [ i ]; } } ll ans = 0 ; for ( int v : d ) ans += 1ll * v * v ; return ans ; } };
```

### Python

```python
class Solution : def minSumSquareDiff ( self , nums1 : List [ int ], nums2 : List [ int ], k1 : int , k2 : int ) -> int : d = [ abs ( a - b ) for a , b in zip ( nums1 , nums2 )] k = k1 + k2 if sum ( d ) <= k : return 0 left , right = 0 , max ( d ) while left < right : mid = ( left + right ) >> 1 if sum ( max ( v - mid , 0 ) for v in d ) <= k : right = mid else : left = mid + 1 for i , v in enumerate ( d ): d [ i ] = min ( left , v ) k -= max ( 0 , v - left ) for i , v in enumerate ( d ): if k == 0 : break if v == left : k -= 1 d [ i ] -= 1 return sum ( v * v for v in d )
```