Watch 7 video solutions for Minimum Sum of Squared Difference, a medium level problem involving Array, Binary Search, Greedy. This walkthrough by codingMohan has 3,478 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.length1 <= n <= 1050 <= nums1[i], nums2[i] <= 1050 <= k1, k2 <= 109Problem Overview: You are given two arrays nums1 and nums2. Each operation decreases any element in either array by 1, up to k1 + k2 total operations. The goal is to minimize the sum of squared differences (nums1[i] - nums2[i])^2 across all indices.
The key observation: operations only matter on the absolute differences diff[i] = |nums1[i] - nums2[i]|. Reducing the largest differences first minimizes the squared penalty because squaring amplifies large values.
Approach 1: Max-Heap to Reduce Largest Differences (O(n log n))
Compute the absolute difference for every index and push them into a heap (priority queue). Always extract the largest difference and reduce it by 1 using one operation. Push the updated value back into the heap and repeat until operations are exhausted or all differences reach zero. This greedy strategy works because decreasing the largest value reduces the squared sum the most at every step. Heap push and pop cost O(log n), giving total time complexity O((n + k) log n) in the worst case and O(n) space.
Approach 2: Greedy Sort and Level Differences (O(n log n))
Instead of repeatedly popping from a heap, sort the difference array in descending order using sorting. Process the largest block of values and reduce them until they match the next smaller difference. This "leveling" technique applies operations in batches instead of one-by-one updates. When operations are insufficient to reach the next level, distribute them evenly across the current largest elements. The idea relies on greedy reduction of the biggest squared contributors. Sorting costs O(n log n), and the adjustment pass runs in O(n) time with O(1) extra space beyond the array.
Approach 3: Binary Search on Maximum Allowed Difference (O(n log m))
Another optimization treats the problem as finding the smallest threshold T such that reducing every diff[i] above T requires at most k1 + k2 operations. Binary search the threshold between 0 and the maximum difference using binary search. For each candidate threshold, iterate through the array and compute how many decrements are required to bring values down to that level. Once the threshold is found, distribute remaining operations across elements at that boundary. The feasibility check runs in O(n), producing overall time complexity O(n log m) where m is the maximum difference, with O(1) extra space.
Recommended for interviews: The max-heap approach is the most intuitive and easiest to implement under pressure. It clearly demonstrates greedy reasoning and correct prioritization of the largest difference. The sorting-based leveling approach is more optimized and reduces repeated heap operations, which interviewers often appreciate once the greedy insight is established.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Max-Heap Reduction | O((n + k) log n) | O(n) | Straightforward greedy implementation that always reduces the largest difference first |
| Greedy Sort and Level | O(n log n) | O(1) | When you want fewer updates by reducing groups of values at once |
| Binary Search Threshold | O(n log m) | O(1) | Useful when reasoning about the maximum allowed difference rather than individual operations |