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.
This approach involves using a max-heap (priority queue) to track and modify the largest differences first. By focusing on reducing the largest differences, we can effectively minimize the impact on the sum of squared differences.
The core idea is to repeatedly decrease the difference that contributes most to the sum of squared differences. We use the combined allowance of k1 and k2 modifications to decrement the largest absolute difference one at a time until we exhaust our allowed modifications or all differences are reduced to zero.
This Python solution uses a max-heap to continuously target and reduce the maximum difference. By working with the negation of the differences, Python's min-heap acts as a max-heap.
The total modifications allowed (k1 + k2) are applied to decrease the largest difference, minimizing the sum of squared differences. This process efficiently finds and modifies the largest element due to the logarithmic complexity of heap operations.
Time Complexity: O(n log n) due to the heap operations over n elements, where insertion and deletion are logarithmic operations.
Space Complexity: O(n) for storing differences in the heap.
This method involves sorting the absolute differences, and then manipulating them starting from the largest. By sorting, we ensure that we are applying our limited operations to the most impactful differences first, similar to the first approach, but without the overhead of maintaining a priority queue.
The total number of operations available (k1 + k2) are progressively applied to reduce these differences, sequentially altering the largest differences first. This leads to minimal squared differences.
This Java solution sorts the absolute differences and iteratively decreases them, starting from the largest, by subtracting up to the number of available modifications.
By sorting, we can handle the most significant differences first, effectively minimizing the sum of squared differences. After applying all modifications, we compute the final result by summing up the squares of the modified differences.
Java
JavaScript
Time Complexity: O(n log n) for sorting the differences.
Space Complexity: O(n) for storing the differences array.
| Approach | Complexity |
|---|---|
| Max-Heap to Minimize Largest Differences | Time Complexity: O(n log n) due to the heap operations over n elements, where insertion and deletion are logarithmic operations. |
| Greedy Sort and Adjust | Time Complexity: O(n log n) for sorting the differences. |
| Default Approach | — |
| 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 |
Biweekly Contest 82 | 6118. Minimum Sum of Squared Difference • codingMohan • 3,478 views views
Watch 6 more video solutions →Practice Minimum Sum of Squared Difference with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor