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 = 0Output
579The arrays cannot be modified because
k1 = 0 and k2 = 0, so the sum is (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 = 1Output
43Increasing
nums1[0] once and nums2[2] once gives squared differences 9 + 16 + 9 + 9 = 43, which is minimum.Constraints
- n == nums1.length == nums2.length
- 1 <= n <= 10^5
- 0 <= nums1[i], nums2[i] <= 10^5
- 0 <= k1, k2 <= 10^9