Problem Description

You have two arrays nums1 and nums2, both containing positive integers and having the same length n. The sum of squared difference between these arrays is calculated by taking the difference between corresponding elements at each position, squaring that difference, and then summing all these squared values. Mathematically, this is: (nums1[0] - nums2[0])² + (nums1[1] - nums2[1])² + ... + (nums1[n-1] - nums2[n-1])².

You're given two additional positive integers k1 and k2 that represent modification budgets:

• You can modify elements in nums1 by adding or subtracting 1, up to k1 times total
• You can modify elements in nums2 by adding or subtracting 1, up to k2 times total

Each modification operation changes a single element by exactly 1 (either +1 or -1). You can apply multiple modifications to the same element, and elements can become negative after modifications.

Your task is to minimize the sum of squared differences by strategically using your available modifications. Return the minimum possible sum of squared differences after using at most k1 modifications on nums1 and at most k2 modifications on nums2.

For example, if nums1 = [1, 2, 3] and nums2 = [4, 2, 1], the initial differences are [-3, 0, 2] and the sum of squared differences is 9 + 0 + 4 = 13. With modifications, you could reduce these differences to minimize the final result.

Intuition

The key insight is that modifying nums1[i] by +1 or -1, or modifying nums2[i] by +1 or -1, both have the same effect: they change the absolute difference |nums1[i] - nums2[i]| by 1. This means we can combine both modification budgets into a single budget k = k1 + k2 and think about reducing the absolute differences directly.

Since we want to minimize the sum of squared differences, and squaring amplifies larger values more than smaller ones, we should prioritize reducing the largest differences first. For example, reducing a difference from 5 to 4 saves us 25 - 16 = 9 in the squared sum, while reducing from 2 to 1 only saves us 4 - 1 = 3.

The problem then becomes: given an array of absolute differences and k operations, how can we minimize the sum of squares? The greedy approach would be to repeatedly reduce the largest difference by 1, but this could be inefficient for large k.

A more efficient approach uses binary search. We can search for the smallest possible maximum value in the final difference array. The idea is: "What's the smallest value x such that we can make all differences at most x using at most k operations?"

For any candidate value mid, we can calculate how many operations are needed to bring all differences down to at most mid. If this requires more than k operations, we need a larger target value. If it requires at most k operations, we might be able to go even smaller.

Once we find this optimal maximum value, we first bring all differences down to this value. If we still have operations left, we distribute them evenly among the elements at this maximum value, reducing them by 1 each, until we run out of operations. This ensures we're always reducing the largest remaining values, which gives us the optimal result.

Learn more about Greedy, Binary Search, Sorting and Heap (Priority Queue) patterns.

Solution Approach

First, we calculate the absolute differences between corresponding elements and store them in array d. Since modifying either array has the same effect on the difference, we combine both budgets: k = k1 + k2.

If the sum of all differences is less than or equal to k, we can reduce all differences to 0, so we return 0 immediately.

Binary Search for Optimal Maximum:

We use binary search to find the smallest possible maximum value that all differences can be reduced to within our budget. The search range is from 0 to max(d).

For each candidate value mid, we check if it's achievable by calculating: sum(max(v - mid, 0) for v in d). This gives us the total operations needed to bring all values down to at most mid. If this sum is less than or equal to k, we can achieve this target, so we search for a potentially smaller value (right = mid). Otherwise, we need a larger target (left = mid + 1).

Apply the Reductions:

After finding the optimal maximum value left, we first reduce all differences to at most this value:

for i, v in enumerate(d):
    d[i] = min(left, v)
    k -= max(0, v - left)

This step uses up some of our operations, and k now contains the remaining operations.

Distribute Remaining Operations:

If we still have operations left (k > 0), we need to distribute them among the elements that are currently at the maximum value left. We iterate through the array and reduce each element at value left by 1, one at a time, until we run out of operations:

for i, v in enumerate(d):
    if k == 0:
        break
    if v == left:
        k -= 1
        d[i] -= 1

This ensures we're always reducing the largest values first, which is optimal for minimizing the sum of squares.

Calculate Final Result:

Finally, we calculate and return the sum of squared differences: sum(v * v for v in d).

The time complexity is O(n log(max(d))) for the binary search, where each check takes O(n) time. The space complexity is O(n) for storing the differences array.

Example Walkthrough

Let's walk through a concrete example with nums1 = [10, 10, 10], nums2 = [3, 3, 3], k1 = 6, and k2 = 6.

Step 1: Calculate initial differences

• Differences: d = [|10-3|, |10-3|, |10-3|] = [7, 7, 7]
• Combined budget: k = k1 + k2 = 12
• Initial sum of squared differences: 7² + 7² + 7² = 147

Step 2: Check if we can reduce everything to 0

• Sum of differences: 7 + 7 + 7 = 21
• Since 21 > 12, we cannot reduce all differences to 0

Step 3: Binary search for optimal maximum

• Search range: left = 0, right = 7

Iteration 1:

• mid = (0 + 7) // 2 = 3
• Operations needed to reduce all values to at most 3: (7-3) + (7-3) + (7-3) = 12
• Since 12 ≤ 12, we can achieve this. Update right = 3

Iteration 2:

• mid = (0 + 3) // 2 = 1
• Operations needed to reduce all values to at most 1: (7-1) + (7-1) + (7-1) = 18
• Since 18 > 12, we cannot achieve this. Update left = 2

Iteration 3:

• mid = (2 + 3) // 2 = 2
• Operations needed to reduce all values to at most 2: (7-2) + (7-2) + (7-2) = 15
• Since 15 > 12, we cannot achieve this. Update left = 3

Iteration 4:

• left = 3, right = 3, search complete

Step 4: Apply reductions to reach maximum of 3

• Reduce each difference from 7 to 3: d = [3, 3, 3]
• Operations used: (7-3) + (7-3) + (7-3) = 12
• Remaining operations: k = 12 - 12 = 0

Step 5: Distribute remaining operations

• Since k = 0, no additional operations to distribute

Step 6: Calculate final result

• Final differences: [3, 3, 3]
• Sum of squared differences: 3² + 3² + 3² = 27

The algorithm successfully reduced the sum of squared differences from 147 to 27 by strategically using all 12 available operations to bring each difference down to 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * log(max(d)))

The algorithm breaks down as follows:

• Creating the difference array d: O(n) where n is the length of nums1/nums2
• Finding the sum of d: O(n)
• Binary search with left and right bounds: O(log(max(d))) iterations
  • Within each binary search iteration, calculating sum(max(v - mid, 0) for v in d): O(n)
  • Total for binary search: O(n * log(max(d)))
• First loop to update d with left value: O(n)
• Second loop to decrement values equal to left: O(n) in worst case
• Final sum calculation: O(n)

The dominant term is O(n * log(max(d))) from the binary search phase.

Space Complexity: O(n)

The space usage includes:

• Array d storing the absolute differences: O(n)
• Other variables (k, left, right, mid): O(1)

The algorithm uses O(n) extra space for storing the differences array, with no additional data structures that scale with input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Distribution of Remaining Operations

The Pitfall: After reducing all differences to the optimal threshold, there may be leftover operations. A common mistake is to arbitrarily distribute these operations or apply them all to a single element, which doesn't minimize the sum of squares optimally.

Why It's Wrong: Consider differences [3, 3, 3] with 2 remaining operations. If you reduce only the first element to get [1, 3, 3], the sum of squares is 1 + 9 + 9 = 19. But if you reduce two elements by 1 each to get [2, 2, 3], the sum is 4 + 4 + 9 = 17, which is better.

The Solution: Always reduce the largest values first, one at a time. In the code, this is handled by:

for i, diff in enumerate(differences):
    if total_operations == 0:
        break
    if diff == optimal_threshold:
        total_operations -= 1
        differences[i] -= 1

This ensures we're spreading the reductions across multiple elements at the maximum value, rather than concentrating them.

2. Off-by-One Error in Binary Search

The Pitfall: Using while min_target <= max_target: instead of while min_target < max_target: can cause an infinite loop or incorrect results when updating boundaries.

Why It's Wrong: With <=, when min_target equals max_target, the loop continues unnecessarily. If you then set min_target = mid_target + 1 or max_target = mid_target - 1, you might skip the optimal value or create inconsistent bounds.

The Solution: Use while min_target < max_target: and update boundaries as:

• max_target = mid_target (not mid_target - 1) when the target is achievable
• min_target = mid_target + 1 when it's not achievable

This ensures convergence to the exact optimal threshold without missing values.

3. Not Handling the Case Where All Differences Can Be Reduced to Zero

The Pitfall: Forgetting to check if sum(differences) <= total_operations at the beginning, leading to unnecessary computation and potentially incorrect results.

Why It's Wrong: If you have enough operations to eliminate all differences completely, the minimum sum of squares is always 0. Without this check, the binary search might find a non-zero threshold, and you'd still have unused operations after the algorithm completes.

The Solution: Always check this condition first:

if sum(differences) <= total_operations:
    return 0

This provides an early exit for cases where complete elimination is possible, improving both correctness and efficiency.