Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2333.html
2333. Minimum Sum of Squared Difference
- Difficulty: Medium.
- Related Topics: Array, Math, Sorting, Heap (Priority Queue).
- Similar Questions: Minimum Absolute Sum Difference, Partition Array Into Two Arrays to Minimize Sum Difference.
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,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 (Java, C++, Python)
-
class Solution { public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) { long minSumSquare = 0; int[] diffs = new int[100_001]; long totalDiff = 0; long kSum = (long) k1 + k2; int currentDiff; int maxDiff = 0; for (int i = 0; i < nums1.length; i++) { // get current diff. currentDiff = Math.abs(nums1[i] - nums2[i]); // if current diff > 0, count/store it. If not,then ignore it. if (currentDiff > 0) { totalDiff += currentDiff; diffs[currentDiff]++; maxDiff = Math.max(maxDiff, currentDiff); } } // if kSum (k1 + k2) < totalDifferences, it means we can make all numbers/differences 0s if (totalDiff <= kSum) { return 0; } // starting from the back, from the highest difference, lower that group one by one to the // previous group. // we need to make all n diffs to n-1, then n-2, as long as kSum allows it. for (int i = maxDiff; i > 0 && kSum > 0; i--) { if (diffs[i] > 0) { // if current group has more differences than the totalK, we can only move k of them // to the lower level. if (diffs[i] >= kSum) { diffs[i] -= kSum; diffs[i - 1] += kSum; kSum = 0; } else { // else, we can make this whole group one level lower. diffs[i - 1] += diffs[i]; kSum -= diffs[i]; diffs[i] = 0; } } } for (int i = 0; i <= maxDiff; i++) { if (diffs[i] > 0) { minSumSquare += (long) (Math.pow(i, 2)) * diffs[i]; } } return minSumSquare; } } ############ class Solution { public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) { int n = nums1.length; int[] d = new int[n]; long s = 0; int mx = 0; int k = k1 + k2; for (int i = 0; i < n; ++i) { d[i] = Math.abs(nums1[i] - nums2[i]); s += d[i]; mx = Math.max(mx, d[i]); } if (s <= k) { return 0; } int left = 0, right = mx; while (left < right) { int mid = (left + right) >> 1; long t = 0; for (int v : d) { t += Math.max(v - mid, 0); } if (t <= k) { right = mid; } else { left = mid + 1; } } for (int i = 0; i < n; ++i) { k -= Math.max(0, d[i] - left); d[i] = Math.min(d[i], left); } for (int i = 0; i < n && k > 0; ++i) { if (d[i] == left) { --k; --d[i]; } } long ans = 0; for (int v : d) { ans += (long) v * v; } return ans; } } -
class Solution: def minSumSquareDiff( self, nums1: List[int], nums2: List[int], k1: int, k2: int ) -> int: d = [abs(a - b) for a, b in zip(nums1, nums2)] k = k1 + k2 if sum(d) <= k: return 0 left, right = 0, max(d) while left < right: mid = (left + right) >> 1 if sum(max(v - mid, 0) for v in d) <= k: right = mid else: left = mid + 1 for i, v in enumerate(d): d[i] = min(left, v) k -= max(0, v - left) for i, v in enumerate(d): if k == 0: break if v == left: k -= 1 d[i] -= 1 return sum(v * v for v in d) ############ # 2333. Minimum Sum of Squared Difference # https://leetcode.com/problems/minimum-sum-of-squared-difference/ class Solution: def minSumSquareDiff(self, nums1: List[int], nums2: List[int], k1: int, k2: int) -> int: pq = [] for a, b in zip(nums1, nums2): heappush(pq, ((-abs(a - b), 1))) orders = k1 + k2 while pq and orders > 0: flag = True top, count = heappop(pq) top = -top while pq and top == -pq[0][0]: count += heappop(pq)[1] nextTop = 0 if pq: nextTop = -pq[0][0] delta = top - nextTop if delta * count <= orders: orders -= (delta * count) else: flag = False heappush(pq, (-top, count)) while pq and orders > 0: x, cnt = heappop(pq) take = min(orders, cnt) orders -= take heappush(pq, (x + 1, take)) if cnt != take: heappush(pq, (x, cnt - take)) if flag and nextTop: heappush(pq, (-nextTop, count)) total = 0 for x, count in pq: total += x * x * count return total -
using ll = long long; class Solution { public: long long minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2) { int n = nums1.size(); vector<int> d(n); ll s = 0; int mx = 0; int k = k1 + k2; for (int i = 0; i < n; ++i) { d[i] = abs(nums1[i] - nums2[i]); s += d[i]; mx = max(mx, d[i]); } if (s <= k) return 0; int left = 0, right = mx; while (left < right) { int mid = (left + right) >> 1; ll t = 0; for (int v : d) t += max(v - mid, 0); if (t <= k) right = mid; else left = mid + 1; } for (int i = 0; i < n; ++i) { k -= max(0, d[i] - left); d[i] = min(d[i], left); } for (int i = 0; i < n && k; ++i) { if (d[i] == left) { --k; --d[i]; } } ll ans = 0; for (int v : d) ans += 1ll * v * v; return ans; } }; -
func minSumSquareDiff(nums1 []int, nums2 []int, k1 int, k2 int) int64 { k := k1 + k2 s, mx := 0, 0 n := len(nums1) d := make([]int, n) for i, v := range nums1 { d[i] = abs(v - nums2[i]) s += d[i] mx = max(mx, d[i]) } if s <= k { return 0 } left, right := 0, mx for left < right { mid := (left + right) >> 1 t := 0 for _, v := range d { t += max(v-mid, 0) } if t <= k { right = mid } else { left = mid + 1 } } for i, v := range d { k -= max(v-left, 0) d[i] = min(v, left) } for i, v := range d { if k <= 0 { break } if v == left { d[i]-- k-- } } ans := 0 for _, v := range d { ans += v * v } return int64(ans) } func abs(x int) int { if x < 0 { return -x } return x } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).