Minimum Sum of Squared Difference

Med

#2125Time: O(n + k * log n). Building the heap takes O(n). The main loop runs `k` times, and each heap operation (poll/add) takes O(log n). Since `k` can be up to `2 * 10^9`, this will be too slow.Space: O(n) to store up to `n` differences in the priority queue.

Patterns

Greedy

Algorithms

Binary Search Sorting

Data structures

Array Heap (Priority Queue)

Prompt

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])² 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 <= 10⁵
0 <= nums1[i], nums2[i] <= 10⁵
0 <= k1, k2 <= 10⁹

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a greedy strategy. The core idea is that to achieve the maximum reduction in the sum of squared differences, we should always decrease the largest current difference. A max heap (Priority Queue in Java) is a natural data structure to efficiently retrieve the largest difference at each step. We simulate the process by repeatedly taking the largest difference, reducing it by one, and putting it back, for a total of k times.

Algorithm

Combine the available operations: k = k1 + k2.
Calculate the absolute difference d[i] = |nums1[i] - nums2[i]| for each pair of elements.
Insert all non-zero differences into a max heap (Priority Queue).
If the total sum of differences is already less than or equal to k, it means we can make all differences zero. The result is 0.
Perform k operations: In a loop that runs k times, extract the maximum element d from the heap, decrease it by one, and insert d-1 back into the heap if it's still positive.
After the loop, the heap contains the final values of the differences.
Calculate the sum of squares of all elements remaining in the heap.

Walkthrough

The problem can be simplified by observing that an operation on nums1 or nums2 has an equivalent effect on the absolute difference |nums1[i] - nums2[i]|. Thus, we can combine k1 and k2 into a single pool of k = k1 + k2 operations, each of which can decrease a difference by 1.

The greedy choice is to always reduce the largest existing difference, as this yields the greatest decrease in the sum of squares. For a difference d, changing it to d-1 reduces the sum of squares by d^2 - (d-1)^2 = 2d - 1, which is maximized when d is maximized.

This leads to a simulation-based approach:

First, calculate all initial absolute differences and store the non-zero ones in a max heap.
Also, compute the total sum of differences. If this sum is less than or equal to k, we can make all differences zero, so the answer is 0.
Otherwise, we loop k times. In each iteration, we extract the largest difference from the heap, decrement it, and re-insert it if it's still greater than zero.
Finally, after exhausting all k operations, we compute the sum of squares of the differences remaining in the heap.

1import java.util.PriorityQueue;2import java.util.Collections;3 4class Solution {5    public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {6        int n = nums1.length;7        long k = k1 + k2;8        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());9        long totalDiff = 0;10 11        for (int i = 0; i < n; i++) {12            int diff = Math.abs(nums1[i] - nums2[i]);13            if (diff > 0) {14                maxHeap.add(diff);15            }16            totalDiff += diff;17        }18 19        if (totalDiff <= k) {20            return 0;21        }22 23        while (k > 0 && !maxHeap.isEmpty()) {24            int maxDiff = maxHeap.poll();25            maxDiff--;26            if (maxDiff > 0) {27                maxHeap.add(maxDiff);28            }29            k--;30        }31 32        long sumOfSquares = 0;33        while (!maxHeap.isEmpty()) {34            long val = maxHeap.poll();35            sumOfSquares += val * val;36        }37        return sumOfSquares;38    }39}

Complexity

Time

O(n + k * log n). Building the heap takes O(n). The main loop runs `k` times, and each heap operation (poll/add) takes O(log n). Since `k` can be up to `2 * 10^9`, this will be too slow.

Space

O(n) to store up to `n` differences in the priority queue.

Trade-offs

Pros

Simple to understand and implement the greedy logic directly.
Correct for all cases, but not always efficient.

Cons

Inefficient for large values of k, as the main loop runs k times, leading to a Time Limit Exceeded (TLE) verdict on platforms with strict time limits.

Instead of simulating the reduction one by one, we can determine the final state of the differences more efficiently. The greedy strategy implies that after all operations, the differences will be "leveled off". All differences will be at most some value T, with some possibly at T and others at T-1. We can use binary search to find the smallest possible value for this threshold T. For a given candidate threshold mid, we can quickly calculate if it's achievable with k operations. This allows us to narrow down the search space for the optimal threshold efficiently.

Algorithm

Calculate the initial absolute differences d[i] = |nums1[i] - nums2[i]|. Let k = k1 + k2.
If the total sum of differences is <= k, return 0.
Binary search for the optimal final maximum difference, let's call it target, in the range [0, max_initial_diff].
For a given mid value in the binary search, define a check(mid) function. This function calculates the total operations needed to make every difference d[i] at most mid. This is sum(d[i] - mid) for all d[i] > mid.
If check(mid) <= k, it means mid is a possible maximum difference. We try for a smaller one by setting high = mid - 1.
If check(mid) > k, mid is too small, we need to allow a larger maximum difference, so we set low = mid + 1.
The binary search will find the smallest threshold T such that we can make all differences at most T.
After finding T, calculate the operations used to reduce all differences greater than T down to T. Let the remaining operations be k_rem.
The final differences will be: d[i] if d[i] < T, and T if d[i] >= T. We use the k_rem operations to reduce k_rem of the differences that are now T down to T-1.
Calculate the final sum of squares based on this new distribution of differences.

Walkthrough

This approach hinges on finding the final state without simulating each step. The greedy strategy ensures that we'll end up with a set of differences where the maximum value is minimized. We can binary search for this final maximum value.

Binary Search: We search for a target difference in the range [0, max_diff]. For a chosen mid, we check if it's possible to make all differences <= mid.
Check Function: To do this, we calculate the operations needed: ops_needed = sum(d - mid) for all differences d > mid. If ops_needed <= k, then mid is achievable, and we can try for an even smaller target. Otherwise, mid is too ambitious, and we need to aim higher.
Final Calculation: Once the binary search finds the smallest possible target, we know that all original differences d > target will be reduced to target. We calculate the operations spent on this, k_used. The remaining operations, k_rem = k - k_used, are then used to reduce k_rem of the target-level differences to target - 1.
The final sum of squares is calculated from this final distribution of differences.

1class Solution {2    public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {3        int n = nums1.length;4        long k = k1 + k2;5        int[] diffs = new int[n];6        long totalDiff = 0;7        int maxDiff = 0;8 9        for (int i = 0; i < n; i++) {10            diffs[i] = Math.abs(nums1[i] - nums2[i]);11            totalDiff += diffs[i];12            maxDiff = Math.max(maxDiff, diffs[i]);13        }14 15        if (totalDiff <= k) {16            return 0;17        }18 19        // Binary search for the target difference20        int low = 0, high = maxDiff;21        int target = 0;22        while (low <= high) {23            int mid = low + (high - low) / 2;24            long opsNeeded = 0;25            for (int d : diffs) {26                if (d > mid) {27                    opsNeeded += (d - mid);28                }29            }30            if (opsNeeded <= k) {31                target = mid;32                high = mid - 1;33            } else {34                low = mid + 1;35            }36        }37 38        // Calculate remaining k and final sum39        long remainingK = k;40        for (int i = 0; i < n; i++) {41            if (diffs[i] > target) {42                remainingK -= (diffs[i] - target);43                diffs[i] = target;44            }45        }46 47        // Distribute remaining k to reduce target to target-148        for (int i = 0; i < n && remainingK > 0; i++) {49            if (diffs[i] == target) {50                diffs[i]--;51                remainingK--;52            }53        }54 55        long sumOfSquares = 0;56        for (int d : diffs) {57            sumOfSquares += (long)d * d;58        }59        return sumOfSquares;60    }61}

Complexity

Time

O(n * log(D)), where `D` is the maximum possible initial difference (e.g., 10^5). The binary search runs `log(D)` times, and inside it, we iterate through `n` differences. This is efficient enough for the given constraints.

Space

O(n) to store the array of differences. This can be optimized to O(1) if we re-calculate differences inside the check function, but at the cost of slightly higher runtime.

Trade-offs

Pros

Much more efficient than the simulation approach for large k.
Avoids the TLE issue by not depending on k for the loop count.

Cons

More complex to reason about and implement correctly compared to the direct simulation.
Slightly less efficient than the frequency counting approach for the given constraints.

This is an optimization of the greedy approach. Instead of processing one difference at a time with a heap, we can process all differences of the same value in a single step. We use a frequency map (or an array, since differences are bounded) to store the counts of each difference value. We then iterate from the largest difference downwards, reducing them in batches. This avoids the logarithmic overhead of a heap and the repeated passes of binary search, making it the most efficient method.

Algorithm

Combine operations: k = k1 + k2.
Calculate absolute differences d[i] = |nums1[i] - nums2[i]|.
Create a frequency array freq of size max_diff + 1, where freq[d] stores the number of times difference d occurs.
If the total sum of differences is <= k, return 0.
Iterate from d = max_diff down to 1.
At each difference d, we have freq[d] elements with this value.
If we have enough operations k to reduce all freq[d] elements from d to d-1 (i.e., k >= freq[d]):
- Use freq[d] operations: k -= freq[d].
- Move the counts: freq[d-1] += freq[d], freq[d] = 0.
If k < freq[d]:
- We can only reduce k of these elements.
- Update counts: freq[d-1] += k, freq[d] -= k.
- Set k = 0 and break the loop, as no more operations are left.
After the loop, the freq array represents the final distribution of differences.
Calculate the sum of squares: sum(d^2 * freq[d]) for all d > 0.

Walkthrough

This approach refines the greedy strategy by processing elements in batches. Instead of a priority queue, we use a frequency array to count occurrences of each difference value. The maximum possible difference is bounded (10^5), making an array feasible.

Frequency Mapping: We first compute all absolute differences and populate a frequency array, freq, where freq[d] holds the number of pairs with difference d.
Greedy Batch Reduction: We iterate downwards from the maximum difference d = max_diff to 1. At each step d, we look at count = freq[d]. These are the largest current differences.
- If we have enough operations (k >= count), we can reduce all of them from d to d-1. We update k by subtracting count and transfer the count from freq[d] to freq[d-1].
- If k < count, we only have enough operations to reduce k of them. We update freq[d] and freq[d-1] accordingly, set k to 0, and stop, as we can't perform any more reductions.
Final Summation: After the loop finishes (either by running out of operations or checking all differences), the freq array holds the final counts of each difference value. The minimum sum of squared differences is the sum of d*d*freq[d] over all d.

1class Solution {2    public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {3        long k = k1 + k2;4        int n = nums1.length;5        int maxDiff = 0;6        long totalDiff = 0;7        8        // Using an array as a frequency map since diff is bounded9        int[] freq = new int[100001]; 10        for (int i = 0; i < n; i++) {11            int diff = Math.abs(nums1[i] - nums2[i]);12            freq[diff]++;13            maxDiff = Math.max(maxDiff, diff);14            totalDiff += diff;15        }16 17        if (totalDiff <= k) {18            return 0;19        }20 21        for (int d = maxDiff; d > 0; d--) {22            if (freq[d] == 0) {23                continue;24            }25            26            long count = freq[d];27            if (k >= count) {28                // Reduce all 'd' differences to 'd-1'29                k -= count;30                freq[d-1] += count;31                freq[d] = 0;32            } else {33                // Reduce 'k' of the 'd' differences to 'd-1'34                freq[d-1] += k;35                freq[d] -= k;36                k = 0;37                break; // No more operations left38            }39        }40 41        long sumOfSquares = 0;42        for (long d = 1; d <= maxDiff; d++) {43            if (freq[(int)d] > 0) {44                sumOfSquares += freq[(int)d] * d * d;45            }46        }47        return sumOfSquares;48    }49}

Complexity

Time

O(n + D), where `D` is the maximum possible initial difference. O(n) to compute differences and build the frequency map, and O(D) to iterate through the frequencies. This is linear and highly efficient.

Space

O(D), where `D` is the maximum possible initial difference (10^5), for the frequency array.

Trade-offs

Pros

Most efficient time complexity among the three approaches.
Conceptually builds on the greedy idea but processes items in batches for superior performance.

Cons

Requires extra space for the frequency map, which depends on the range of differences, not just the input size n.

Solutions

Solution

1class 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 ; } }

1using 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 ; } };

1class 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 )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class 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 ; } }

1using 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 ; } };

1class 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 )

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.