LeetCode 2333 · Minimum Sum of Squared Difference ↗

Minimum Sum of Squared Difference

Two arrays, k1 + k2 single-step nudges, and one squared bill — spend every nudge where the gap is biggest.

The memory hook

Pool k1 + k2 into a single budget and spend every move on the current largest gap.

MediumGreedy max-first + frequency levelsO(n + D) timeO(n) space
01

Squares punish the biggest gap most

intuition

Only the gaps d = |nums1[i] − nums2[i]| matter — never which array you nudge, since +1 here and −1 there shrink the same gap. Shrinking a gap from d to d−1 cuts the bill by d² − (d−1)² = 2d−1, which grows with d. So the single most valuable move is always on the current maximum, and the whole problem becomes draining a pile of gaps from the top.

1Pool the budgets+1 on nums1[i] and −1 on nums2[i] both shrink gap i by one, so k1 and k2 merge into one shared pile of k = k1 + k2 moves.
2Always hit the maxEach move's saving is 2d−1, largest at the largest d. Any move spent on a smaller gap can be swapped upward without losing — the greedy choice never regrets.
3Settle the leftoversIf moves outnumber the total gap, everything reaches zero and spare moves just bounce one gap between 0 and 1 — so the answer is the leftover parity.
The one sentence to remember: because every unit of reduction is worth more at a taller gap, the pile drains from the top down with zero regret, and only the parity of unspent moves survives the drain.
02

Watch the top level drain

playable trace

Each frame drains one gap level exactly like the Counter loop below: whole levels fall at once, a short budget takes a partial bite, and the Σd² readout ticks down to the answer. Enter any two equal-length arrays plus the pooled budget k.

Playable trace · greedy max-first
Frames are generated from the same logic as the code below.
Presets
Current event
Ready — press Play
Σ d² now
0
Gap levels (top first)
Press Play to drain the gaps from the top down.
settled reduced this step at current max bounced by leftovers final gaps
0 / 0
03

Drain levels, not single moves

the solution
Python · greedy max-first + frequency levels
class Solution:
    def minSumSquareDiff(self, nums1, nums2, k1, k2):
        from collections import Counter
        k = k1 + k2  # one shared budget: +1 here == -1 there
        diffs = [abs(a - b) for a, b in zip(nums1, nums2)]
        total = sum(diffs)
        if k >= total:
            return (k - total) % 2  # leftovers bounce 0 -> 1 -> 0 ...
        freq = Counter(diffs)
        for d in range(max(diffs), 0, -1):  # drain from the top
            c = freq[d]
            if not c:
                continue
            t = min(c, k)  # whole level, or one partial bite
            freq[d] -= t
            freq[d - 1] += t
            k -= t
            if k == 0:
                break
        return sum(d * d * c for d, c in freq.items())

The trace above runs this same loop: whole-level drops, at most one partial bite, and the parity shortcut for leftover moves.

Leftover bouncek ≥ sum(diffs) → (k − sum) % 2Spare moves can't push below zero, so each extra move flips one gap 0→1→0…; an odd leftover strands a single 1.
Whole or partialt = min(count, k)A level either falls intact or absorbs the final moves. There is never a reason to skip a level and shave a smaller gap instead.
Richest saving firstsaving = 2d − 1Shrinking d to d−1 earns 2d−1, so the top level always pays best. That formula is the whole exchange argument in one line.
Why is max-first optimal? Exchange argument: take any optimal plan whose first move isn't on a max gap d*. Moving that unit onto d* changes its saving from 2d−1 to 2d*−1 ≥ 2d−1, so some optimal plan starts greedy — then induct on the rest.
TimeO(n + D)One pass builds the gaps and their counts; the loop walks down from the max gap D (≤ 10⁵) touching each level once — no per-move heap pops even when k hits 10⁹.
SpaceO(n)The gaps array plus the frequency table, both linear in n.
04

Two quick mental checks

make it stick
[1,2,3,4] vs [2,10,20,19], k = 0
→ 579

No moves to spend, so the bill is just 1 + 64 + 289 + 225. The trace is two frames: start, done — greediness needs no moves to be correct.

[1,4,10,12] vs [5,8,6,9], k = 2
→ 43

Gaps start [4,4,4,3]; both moves bite level 4, leaving [4,3,3,3] for 16 + 9+9+9 = 43. Any other placement of the same two moves scores worse — try it in the trace.

What to say out loud
I pool both operation counts into one budget since only the absolute gaps matter, then repeatedly shave the current largest gap — each unit there saves the most — draining level by level with a frequency table, and if moves outlast the total gap the answer is just the leftover parity.