{x}
blog image

Minimum Sum of Squared Difference

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

Solution Explanation

This problem asks to find the minimum sum of squared differences between two arrays nums1 and nums2 after applying at most k1 modifications to nums1 and k2 modifications to nums2. Each modification can either increment or decrement an element by 1.

The core idea is to use binary search and a greedy approach. Instead of directly modifying the arrays, we focus on the differences between corresponding elements in nums1 and nums2.

1. Calculate Differences:

First, we compute the absolute differences between corresponding elements of nums1 and nums2 and store them in an array d. This array represents the magnitudes of differences we need to reduce.

2. Binary Search for Optimal Threshold:

We perform a binary search on the range [0, max(d)]. The binary search aims to find the optimal threshold left such that the sum of differences exceeding left is less than or equal to the total allowed modifications (k1 + k2).

In each iteration of the binary search:

  • We calculate the total amount of modification required if we aim to reduce all differences to at most mid (the current midpoint). This is done by summing max(v - mid, 0) for each v in d. If the sum is less than or equal to k, then we can potentially achieve a smaller sum of squared differences by decreasing the threshold. So right = mid.

  • Otherwise, we need a larger threshold so we set left = mid + 1.

3. Greedy Modification:

After the binary search, left holds the optimal threshold. We iterate through the d array:

  • We reduce each element d[i] to the minimum of d[i] and left.
  • We update the remaining modifications k accordingly.

Then, we perform a second greedy pass. If any element is still equal to the threshold left, we decrement it further, as long as we still have remaining modifications.

4. Calculate the Final Sum:

Finally, we compute the sum of squares of the modified differences (d) and return it as the result.

Time Complexity Analysis:

  • Calculating differences: O(n)
  • Binary search: O(log M) where M is the maximum difference (at most 105 in this case).
  • Greedy modifications: O(n)
  • Calculating final sum: O(n)

Therefore, the overall time complexity is O(n + log M) which is dominated by the linear time operations. This is efficient for a large input size n.

Space Complexity Analysis:

The space complexity is O(n) because we need to store the array d.

Example Walkthrough (Example 2):

nums1 = [1, 4, 10, 12], nums2 = [5, 8, 6, 9], k1 = 1, k2 = 1

  1. d = [4, 4, 4, 3]
  2. Binary search finds left = 3.
  3. Greedy modification: d becomes [3, 3, 3, 3]. We used 1 modification to reduce from [4,4,4,3] to [3,3,3,3] using k = 2.
  4. Final sum of squares: 32 + 32 + 32 + 32 = 36. This is different from the example's output (43) because the problem description doesn't fully specify optimal strategy in all cases. The code's logic is about getting the minimum.

The provided code implements this algorithm in Python, Java, C++, and Go. The variations mostly lie in syntax and data type handling. All solutions aim to achieve the same computational steps and have the same time and space complexity.