#2333

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Minimum Sum of Squared Difference

Calculate the minimum sum of squared differences between two arrays using limited modifications and binary search techniques.

array binary search greedy sorting heap priority queue

Problem Statement

You are given two integer arrays nums1 and nums2, both of length n. You can modify any element of nums1 or nums2 by +1 or -1 a limited number of times defined by k1 and k2.

Your goal is to minimize the sum of squared differences defined as the sum of (nums1[i] - nums2[i])^2 for all indices i. Determine the minimum sum achievable after applying at most k1 modifications to nums1 and k2 modifications to nums2.

Examples

Example 1

Input: nums1 = [1,2,3,4], nums2 = [2,10,20,19], k1 = 0, k2 = 0

Output: 579

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

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 Approach

Calculate initial differences and prioritize

Compute the absolute differences between nums1 and nums2 for each index. Use a max-heap to always reduce the largest difference first, since decreasing larger differences yields the biggest reduction in squared sum.

Apply binary search over valid sum range

Perform binary search on the possible maximum difference to determine the minimal achievable sum. Each iteration checks if the current target sum can be reached using the total available modifications k1 + k2, which treats both modification counts as interchangeable.

Greedy adjustments to reach minimum

Iteratively reduce differences starting from the largest, using the remaining modification count. Stop when no modifications remain or all differences are zero, ensuring the final sum of squares is minimized.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log D) where D is the maximum difference between nums1 and nums2, due to binary search combined with heap operations. Space complexity is O(n) to store differences and the max-heap.

What Interviewers Usually Probe

Focus on reducing the largest differences first.
Consider k1 and k2 as interchangeable resources.
Binary search is intended over the valid squared sum range.

Common Pitfalls or Variants

Common pitfalls

Failing to combine k1 and k2 for total modifications, treating them separately.
Attempting to greedily adjust without tracking the largest difference first.
Miscomputing the squared sum after adjustments, missing zero-floor constraints.

Follow-up variants

Allow only increasing elements in nums1 and decreasing in nums2.
Limit modifications to specific indices rather than all elements.
Change the cost function to weighted squared differences or absolute differences.

FAQ

What pattern does Minimum Sum of Squared Difference rely on?

It relies on binary search over the valid answer space combined with a greedy reduction of largest differences.

Can k1 and k2 be used interchangeably?

Yes, adding +1 to nums1 or subtracting -1 from nums2 has the same effect on the absolute difference.

What is the best data structure to track differences?

A max-heap is ideal to always access and reduce the largest difference first for maximum squared sum reduction.

How do I verify the final sum is minimal?

After applying all allowed modifications greedily, compute the sum of squares. No further reduction is possible if all differences are zero or all modifications are used.

What is a common mistake in solving this problem?

Treating k1 and k2 separately or reducing smaller differences first, which leads to a higher final squared sum.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

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)

Continue Practicing

#1648 sell diminishing valued colored balls #2335 minimum amount of time to fill cups #2357 make array zero by subtracting equal amounts