How to Solve Minimum Sum of Squared Difference

This problem requires minimizing the sum of squared differences between nums1 and nums2 by modifying elements with a limited number of +1 or -1 operations. The strategy involves reducing the largest differences first, which naturally leads to a greedy approach. Binary search over the valid answer space efficiently determines the smallest achievable squared sum after all allowed modifications.

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

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.

How GhostInterview Helps

• Automatically prioritizes differences and applies binary search over the achievable sum space.
• Calculates the optimal greedy adjustments to minimize squared sum efficiently.
• Provides intermediate reasoning for each adjustment, avoiding manual heap management errors.

Topic Pages

• Array
• Binary Search
• Greedy
• Sorting
• Heap (Priority Queue)

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.