Minimum Sum of Squared Difference

Minimum Sum of Squared Difference

What is this problem about?

The Minimum Sum of Squared Difference problem gives you two integer arrays of equal length and a budget of k total operations. In each operation, you can decrease any element of the first array by 1. After using at most k operations, compute the minimum possible sum of squared differences: sum((arr1[i] - arr2[i])^2). This Minimum Sum of Squared Difference coding problem requires greedy budget allocation using a max-heap.

Why is this asked in interviews?

Uber, Microsoft, and Amazon ask this to test heap-based greedy strategies under a budget constraint. The key insight — that you should always reduce the largest current difference first, since squaring makes large values disproportionately costly — demonstrates understanding of the convexity of the squared function. The array, sorting, binary search, heap, and greedy interview pattern is central.

Algorithmic pattern used

Use a max-heap based on absolute differences |arr1[i] - arr2[i]|. In each operation, extract the largest difference, reduce it by 1 (or reduce it by as much as possible within the remaining budget), and push back the updated difference. To optimize, instead of reducing one step at a time, compute how many steps it takes to bring the top element equal to the second-largest. Perform that many reductions at once, then distribute remaining budget proportionally across elements at the same level.

Example explanation

arr1 = [1, 4, 10], arr2 = [2, 4, 7], k = 3. Differences: |1-2|=1, |4-4|=0, |10-7|=3.

• Reduce diff 3 by 3 steps (all of k): diff becomes 0. Sum of squares = 1² + 0² + 0² = 1.

Common mistakes candidates make

• Reducing by 1 in each iteration rather than computing bulk reductions.
• Not accounting for the case where a difference reaches 0 (don't continue reducing past 0).
• Ignoring the ordering of reductions (must always reduce the largest difference first).
• Miscomputing the squared sum after operations.

Interview preparation tip

When minimizing a sum of squared (or convex) values under a budget of reductions, always reduce the largest value first — this is the greedy choice that minimizes total squared sum due to convexity. The heap provides efficient access to the current maximum. Practice bulk-reduction optimization to avoid TLE on large k values — the step of "reduce all top-k equal maximums simultaneously" is the key efficiency improvement.