Loading 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 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,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1
Output: 43
Explanation: The gaps are 4, 4, 4, 3 and the shared budget is 2. Spending both units on two of the 4s brings them to 3, giving gaps 3, 3, 4, 3 and a squared sum of 9 + 9 + 16 + 9 = 43.
Example 2
Input: nums1 = [1,2,3,4], nums2 = [2,10,20,19], k1 = 0, k2 = 0
Output: 579
Explanation: With no budget nothing can change, so the answer is just the raw squared difference: 1 + 64 + 289 + 225 = 579.
Example 3
Input: nums1 = [5,5,5], nums2 = [1,1,1], k1 = 6, k2 = 0
Output: 12
Explanation: Each gap is 4 (total 12) and the budget is 6. Shaving every gap down to 2 costs exactly 6, leaving gaps 2, 2, 2 and a squared sum of 4 + 4 + 4 = 12.
Only the absolute gaps d[i] = |nums1[i] - nums2[i]| matter, and the total budget is k = k1 + k2. Spending a unit on the largest gap always saves the most, so the optimal result caps every gap at some ceiling m (with a little leftover budget pushing a few of them one lower). Binary search finds the smallest affordable ceiling in O(n log(maxGap)).
Run checks all cases above. Submit evaluates all test cases.