2333. Minimum Sum of Squared Difference

2026, Oct 10 2 mins read

1. Description

Given two integer arrays nums1 and nums2 of equal length n, minimize the sum of $(nums1[i] - nums2[i])^2$ over all indices.
Each operation increases or decreases one element by 1. You may perform up to k1 operations on nums1 and up to k2 operations on nums2.
Return the smallest achievable squared-difference sum. Modified elements may be negative, and unused operations are allowed.

2. Example

Example 1

Input: nums1 = [1,2,3,4], nums2 = [2,10,20,19], k1 = 0, k2 = 0
Output: 579
Explanation: With no operations available, the result is $1^2 + 8^2 + 17^2 + 15^2 = 579$.

Example 2

Input: nums1 = [1,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1
Output: 43
Explanation: Increment nums1[0] and nums2[2]. The resulting absolute differences are [3,4,3,3], giving $9 + 16 + 9 + 9 = 43$.

3. Constraints

n == nums1.length == nums2.length
1 <= n <= $10^5$
0 <= nums1[i], nums2[i] <= $10^5$
0 <= k1, k2 <= $10^9$

4. Solutions

Greedy with Counting Buckets

n = nums1.size(), U = 100001
Time complexity: O(n + U)
Space complexity: O(U)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Reducing a difference d by 1 saves 2d - 1, so reduce the largest differences first.
// Combine k1 and k2, then move counts to lower buckets from largest to smallest.
class Solution {
public:
    long long minSumSquareDiff(const vector<int> &nums1, const vector<int> &nums2, int k1, int k2) {
        const int n = nums1.size();
        int64_t k = static_cast<int64_t>(k1) + static_cast<int64_t>(k2);
        array<int, 100001> count{0};
        int max_diff = 0;
        for (int i = 0; i < n; ++i) {
            int diff = abs(nums1[i] - nums2[i]);

            max_diff = max(max_diff, diff);
            ++count[diff];
        }

        int max_index = max_diff;
        for (int i = max_diff; i > 0 && k > 0; --i) {
            int64_t moves = min(k, static_cast<int64_t>(count[i]));

            count[i] -= moves;
            count[i - 1] += moves;
            k -= moves;
            max_index = i;
        }

        long long sum = 0;
        for (int i = max_index; i > 0; --i) {
            sum += static_cast<long long>(count[i]) * i * i;
        }

        return sum;
    }
};

Search

Tags