Minimum Sum of Squared Difference LeetCode solution in C++

1
class Solution {
2
 public:
3
  long long minSumSquareDiff(vector<int> &nums1, vector<int> &nums2, int k1, int k2) {
4
    int n = nums1.size();
5
    vector<int> diff(n);
6
    for (int i = 0; i < n; ++i) {
7
      diff[i] = abs(nums1[i] - nums2[i]);
8
    }
9
    int M = *max_element(diff.begin(), diff.end());
10
    vector<int> bucket(M + 1);
11
    for (int i = 0; i < n; ++i) {
12
      bucket[diff[i]]++;
13
    }
14
    int k = k1 + k2;
15
    for (int i = M; i > 0; --i) {
16
      if (bucket[i] > 0) {
17
        int minus = min(bucket[i], k);
18
        bucket[i] -= minus;
19
        bucket[i - 1] += minus;
20
        k -= minus;
21
      }
22
    }
23
    long long ans = 0;
24
    for (long long i = M; i > 0; --i) {
25
      ans += bucket[i] * i * i;
26
    }
27
    return ans;
28
  }
29
};