304 North Cardinal St.
Dorchester Center, MA 02124

# Minimum Sum of Squared Difference LeetCode Solution

## Problem – Minimum Sum of Squared Difference LeetCode Solution

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 once.
- Increase nums2 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`

### Minimum Sum of Squared Difference LeetCode Solution in C++

``````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;
}
};
``````

### Minimum Sum of Squared Difference LeetCode Solution in Java

``````class Solution {
public:
#define ll long long
long long minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2) {
int n = nums1.size();
unordered_map<ll, ll> mp;
for(int i = 0; i < n; ++i) {
mp[abs(nums1[i] - nums2[i])]++;
}
long long tot = k1 + k2;

priority_queue<array<ll, 2>> pq;
for(auto [x, y]: mp) {
if(x == 0) continue;
pq.push({x, y});
}

while(!pq.empty() and tot > 0) {
array<ll, 2> v = pq.top();
pq.pop();

if(pq.size() == 0) {
ll mn = min(tot, v);
tot -= mn;
v -= mn;
if(v - 1 > 0) pq.push({v - 1, mn});
if(v > 0) pq.push(v);
} else {
ll mn = min(tot, v);
tot -= mn;
v -= mn;
if(v > 0) pq.push(v);

if(pq.top() == v - 1) {
array<ll, 2> v1 = pq.top();
pq.pop();
v1 += mn;
pq.push(v1);
} else if(v - 1 > 0) {
pq.push({v - 1, mn});
}
}
}

ll ans = 0;
while(!pq.empty()) {
array<ll, 2> v = pq.top();
ans += v * v * v;
pq.pop();
}
return ans;
}
};
``````

### Minimum Sum of Squared Difference LeetCode Solution in Python

``````from heapq import heapify, heappush, heappop
class Solution:
def minSumSquareDiff(self, nums1: List[int], nums2: List[int], k1: int, k2: int) -> int:
heap = [ -abs(x-y) for x, y in zip(nums1, nums2)]
s = -sum(heap)
if k1+k2 >= s: return 0
delta = k1 + k2
heapify(heap)
n = len(nums1)
while delta > 0:
d = -heappop(heap)
gap = max(delta//n, 1) if heap else delta
d -= gap
heappush(heap, -d)
delta -= gap
return sum(pow(e,2) for e in heap)
``````
##### Minimum Sum of Squared Difference LeetCode Solution Review:

In our experience, we suggest you solve this Minimum Sum of Squared Difference LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Minimum Sum of Squared Difference LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Minimum Sum of Squared Difference LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions