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 minimumsum of squared difference after modifying array _nums1 at mostk1 times and modifying arraynums2 at mostk2 times.

Note : You are allowed to modify the array elements to become negative integers.

Examples

Example 1

1
2
3
4

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

1
2
3
4
5
6
7
8

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 <= 10^5
  • 0 <= nums1[i], nums2[i] <= 10^5
  • 0 <= k1, k2 <= 10^9

Solution

Method 1 – Greedy with Frequency Counting

Intuition

To minimize the sum of squared differences, we should reduce the largest differences first. We can use a frequency array to count the occurrences of each difference, then greedily reduce the largest differences using available operations.

Approach

  1. Compute the absolute differences for each index.
  2. Count the frequency of each difference.
  3. Use k1 + k2 operations to reduce the largest differences, one at a time.
  4. After all operations, compute the sum of squares of the remaining differences.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    long long minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2) {
        int n = nums1.size(), k = k1 + k2;
        vector<int> diff(n);
        for (int i = 0; i < n; ++i) diff[i] = abs(nums1[i] - nums2[i]);
        vector<long long> freq(100001, 0);
        for (int d : diff) freq[d]++;
        for (int i = 100000; i > 0 && k > 0; --i) {
            long long take = min((long long)freq[i], (long long)k);
            freq[i] -= take;
            freq[i-1] += take;
            k -= take;
        }
        long long ans = 0;
        for (int i = 0; i <= 100000; ++i) ans += freq[i] * i * i;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func minSumSquareDiff(nums1, nums2 []int, k1, k2 int) int64 {
    n := len(nums1)
    k := k1 + k2
    freq := make([]int64, 100001)
    for i := 0; i < n; i++ {
        d := abs(nums1[i]-nums2[i])
        freq[d]++
    }
    for i := 100000; i > 0 && k > 0; i-- {
        take := min(int64(freq[i]), int64(k))
        freq[i] -= take
        freq[i-1] += take
        k -= int(take)
    }
    var ans int64
    for i := 0; i <= 100000; i++ {
        ans += freq[i] * int64(i) * int64(i)
    }
    return ans
}
func abs(a int) int { if a < 0 { return -a } else { return a } }
func min(a, b int64) int64 { if a < b { return a } else { return b } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {
        int n = nums1.length, k = k1 + k2;
        long[] freq = new long[100001];
        for (int i = 0; i < n; i++) freq[Math.abs(nums1[i]-nums2[i])]++;
        for (int i = 100000; i > 0 && k > 0; i--) {
            long take = Math.min(freq[i], k);
            freq[i] -= take;
            freq[i-1] += take;
            k -= take;
        }
        long ans = 0;
        for (int i = 0; i <= 100000; i++) ans += freq[i] * i * i;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun minSumSquareDiff(nums1: IntArray, nums2: IntArray, k1: Int, k2: Int): Long {
        val n = nums1.size; var k = k1 + k2
        val freq = LongArray(100001)
        for (i in 0 until n) freq[kotlin.math.abs(nums1[i]-nums2[i])]++
        for (i in 100000 downTo 1) {
            if (k == 0) break
            val take = minOf(freq[i], k.toLong())
            freq[i] -= take
            freq[i-1] += take
            k -= take.toInt()
        }
        var ans = 0L
        for (i in 0..100000) ans += freq[i] * i * i
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def minSumSquareDiff(self, nums1: list[int], nums2: list[int], k1: int, k2: int) -> int:
        from collections import Counter
        n, k = len(nums1), k1 + k2
        diff = [abs(a-b) for a,b in zip(nums1, nums2)]
        freq = Counter(diff)
        for i in range(100000, 0, -1):
            take = min(freq[i], k)
            freq[i] -= take
            freq[i-1] += take
            k -= take
        return sum(v*i*i for i,v in freq.items())
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn min_sum_square_diff(nums1: Vec<i32>, nums2: Vec<i32>, k1: i32, k2: i32) -> i64 {
        let n = nums1.len(); let mut k = k1 + k2;
        let mut freq = vec![0i64; 100001];
        for i in 0..n { freq[(nums1[i]-nums2[i]).abs() as usize] += 1; }
        for i in (1..=100000).rev() {
            if k == 0 { break; }
            let take = freq[i].min(k as i64);
            freq[i] -= take;
            freq[i-1] += take;
            k -= take as i32;
        }
        let mut ans = 0i64;
        for i in 0..=100000 { ans += freq[i] * (i as i64) * (i as i64); }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    minSumSquareDiff(nums1: number[], nums2: number[], k1: number, k2: number): number {
        const n = nums1.length, k = k1 + k2;
        const freq = Array(100001).fill(0);
        for (let i = 0; i < n; i++) freq[Math.abs(nums1[i]-nums2[i])]++;
        let ops = k;
        for (let i = 100000; i > 0 && ops > 0; i--) {
            const take = Math.min(freq[i], ops);
            freq[i] -= take;
            freq[i-1] += take;
            ops -= take;
        }
        let ans = 0;
        for (let i = 0; i <= 100000; i++) ans += freq[i] * i * i;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n + D) — n for difference calculation, D=100000 for frequency reduction.
  • 🧺 Space complexity: O(D) — For frequency array.