Skip to content

2333. Minimum Sum of Squared Difference

SourceBiweekly Contest 82 Q3DifficultyMediumRating2011

Description

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

Solutions

Solution 1: Greedy + Counting

Thinking

One \(\pm 1\) on either array decreases the absolute difference at that index by one, so \(k_1\) and \(k_2\) form a single budget \(k\). With \(n \le 10^5\) and up to \(2 \times 10^9\) operations, simulating each step or maintaining a heap of the current maxima is too slow.

The square is strictly convex, so the same operation reduces the sum of squares by more when it is applied to a larger difference. Differences lie in \([0, 10^5]\), and equal values can be lowered together.

Count the frequency of each difference and scan from the largest downward: if the remaining budget covers a whole level, merge that level into the next lower value; otherwise spend what is left and stop. When the sum of differences is already at most \(k\), the answer is \(0\).

Set \(k = k_1 + k_2\) and let \(d_i = |nums1_i - nums2_i|\). If the sum of these differences is at most \(k\), every difference can be reduced to \(0\) and the answer is \(0\).

Otherwise, record the frequency of each difference in \(cnt\), and let \(m\) be the maximum difference. Scan \(v\) downward from \(m\): this level contains \(cnt[v]\) values, and \(\textit{take} = \min(cnt[v], k)\) of them can be decreased by one. Move those \(\textit{take}\) counts to \(v - 1\) and subtract \(\textit{take}\) from \(k\). Stop when \(k\) is exhausted.

The answer is \(\sum_v v^2 \cdot cnt[v]\).

The time complexity is \(O(n + M)\) and the space complexity is \(O(M)\), where \(n\) is the array length and \(M\) is the maximum difference. In this problem, \(M \le 10^5\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def minSumSquareDiff(
        self, nums1: List[int], nums2: List[int], k1: int, k2: int
    ) -> int:
        k = k1 + k2
        s = mx = 0
        cnt = [0] * 100001
        for a, b in zip(nums1, nums2):
            v = abs(a - b)
            cnt[v] += 1
            s += v
            mx = max(mx, v)
        if s <= k:
            return 0
        for v in range(mx, 0, -1):
            if cnt[v] == 0:
                continue
            take = min(cnt[v], k)
            k -= take
            cnt[v] -= take
            cnt[v - 1] += take
            if k == 0:
                break
        return sum(v * v * cnt[v] for v in range(mx + 1))

 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
class Solution {
    public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {
        int k = k1 + k2;
        long s = 0;
        int mx = 0;
        int[] cnt = new int[100001];
        for (int i = 0; i < nums1.length; ++i) {
            int v = Math.abs(nums1[i] - nums2[i]);
            ++cnt[v];
            s += v;
            mx = Math.max(mx, v);
        }
        if (s <= k) {
            return 0;
        }
        for (int v = mx; v > 0 && k > 0; --v) {
            if (cnt[v] == 0) {
                continue;
            }
            int take = Math.min(cnt[v], k);
            k -= take;
            cnt[v] -= take;
            cnt[v - 1] += take;
        }
        long ans = 0;
        for (int v = 0; v <= mx; ++v) {
            ans += (long) v * v * cnt[v];
        }
        return ans;
    }
}

 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
class Solution {
public:
    long long minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2) {
        int k = k1 + k2;
        long long s = 0;
        int mx = 0;
        vector<int> cnt(100001);
        for (int i = 0; i < nums1.size(); ++i) {
            int v = abs(nums1[i] - nums2[i]);
            ++cnt[v];
            s += v;
            mx = max(mx, v);
        }
        if (s <= k) {
            return 0;
        }
        for (int v = mx; v > 0 && k > 0; --v) {
            if (cnt[v] == 0) {
                continue;
            }
            int take = min(cnt[v], k);
            k -= take;
            cnt[v] -= take;
            cnt[v - 1] += take;
        }
        long long ans = 0;
        for (int v = 0; v <= mx; ++v) {
            ans += 1LL * v * v * cnt[v];
        }
        return ans;
    }
};

 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
35
36
func minSumSquareDiff(nums1 []int, nums2 []int, k1 int, k2 int) int64 {
    k := k1 + k2
    var s int64
    mx := 0
    cnt := make([]int, 100001)
    for i, a := range nums1 {
        v := abs(a - nums2[i])
        cnt[v]++
        s += int64(v)
        mx = max(mx, v)
    }
    if s <= int64(k) {
        return 0
    }
    for v := mx; v > 0 && k > 0; v-- {
        if cnt[v] == 0 {
            continue
        }
        take := min(cnt[v], k)
        k -= take
        cnt[v] -= take
        cnt[v-1] += take
    }
    var ans int64
    for v := 0; v <= mx; v++ {
        ans += int64(v) * int64(v) * int64(cnt[v])
    }
    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Comments