`k1` and `k2` look like two budgets and they are one. Adding 1 to `nums1[i]` and subtracting 1 from `nums2[i]` do the same thing to `|nums1[i] - nums2[i]|`, so the only quantity that matters is `k = k1 + k2`: that many unit decrements, spendable on any gap. Widening a gap is never useful, and pushing one past zero into negative territory only makes the square grow again, so each unit either shrinks a positive gap by 1 or is wasted. What's left is water-filling on the multiset of gaps. Dropping a gap `d` by one buys `d^2 - (d-1)^2 = 2d - 1`, which is largest for the largest `d`, so the optimum always attacks the current maximum. Run that to exhaustion and the shape of the answer is a flat ceiling: some cap `t` where every gap above it has collapsed to `t`, and whatever budget survived pushes a few of those one step further to `t - 1`. The naive reading of that greedy is a max-heap: pop the top, decrement, push it back, repeat `k` times. With `k` up to `2 * 10^9` that loop never returns. Binary searching the ceiling costs `O(log)` evaluations of `cost(t) = sum of max(0, d - t)`, and because the gaps are bounded by `10^5`, a counting array with suffix sums answers each evaluation in constant time. ## Worked example `nums1 = [1,4,10,12]`, `nums2 = [5,8,6,9]`, `k1 = k2 = 1`. The gaps are `4, 4, 4, 3`, summing to 15 against a budget of 2, so flattening everything to zero is out of reach. - `cost(4) = 0` — the ceiling 4 is already satisfied and the budget is untouched - `cost(3) = 3` — the three gaps of 4 each need one step, which overshoots 2 The smallest reachable ceiling is `t = 4`, with `leftover = 2` units unspent and `m = 3` gaps sitting at 4. Two of those take one more step down to 3: `3^2 + 4^2 + 3^2 + 3^2` = 9 + 16 + 9 + 9 = 43, the expected output. ## Complexity - **Time** O(n + M + log M) with `M = 10^5` — one pass over the pairs, one suffix sweep over the value range, one binary search on top. - **Space** O(M) — three arrays indexed by gap value; the number of pairs never enters. ## Code (C++) ```cpp class Solution { public: long long minSumSquareDiff(vector& nums1, vector& nums2, int k1, int k2) { const int M = 100000; // a gap can never exceed 1e5 long long k = (long long)k1 + k2; // both budgets spend on the same gaps long long totalDiff = 0; vector cnt(M + 2, 0); int n = nums1.size(); for (int i = 0; i < n; ++i) { int d = abs(nums1[i] - nums2[i]); cnt[d]++; totalDiff += d; } if (totalDiff <= k) return 0; // every gap can be flattened vector cntGE(M + 2, 0), sumGE(M + 2, 0); for (int v = M; v >= 0; --v) { cntGE[v] = cntGE[v + 1] + cnt[v]; sumGE[v] = sumGE[v + 1] + (long long)v * cnt[v]; } auto cost = [&](int t) { // ops needed to cap every gap at t return sumGE[t + 1] - (long long)t * cntGE[t + 1]; }; int lo = 1, hi = M; // t = 0 handled by the early return while (lo < hi) { int mid = lo + (hi - lo) / 2; if (cost(mid) <= k) hi = mid; else lo = mid + 1; } long long t = lo; long long leftover = k - cost(lo); // strictly smaller than the pile at t long long m = cntGE[lo]; // how many gaps sit at t after capping long long ans = 0; for (int v = 1; v < lo; ++v) ans += (long long)v * v * cnt[v]; ans += (m - leftover) * t * t + leftover * (t - 1) * (t - 1); return ans; } }; ``` ## One note The early `return 0` is load-bearing, not a shortcut. The search starts at `lo = 1`, so when the budget covers every gap the binary search still reports `t = 1`, and then `leftover = k - cost(1)` comes out bigger than `m`. The term `(m - leftover) * t * t` goes negative and the function returns a negative sum of squares. A negative answer is at least an honest failure; what makes it worth guarding explicitly is that it only appears on inputs where the answer is 0, which no small hand-written test tends to cover. Everywhere else the inequality `leftover < m` holds, and it's worth seeing why instead of trusting it. `t` is minimal, so `cost(t - 1) > k`, and `cost(t - 1) = cost(t) + cntGE[t]` — lowering the ceiling by one costs exactly one extra unit for every gap at or above `t`. Subtracting, `leftover = k - cost(t) < cntGE[t] = m`. The leftover can never exhaust the pile it draws from, which is why the final line needs no clamping. The other trap is width. `10^5` gaps of `10^5` is `10^15`, so the accumulator has to be 64-bit — and so does each product. In `(long long)v * v * cnt[v]` the cast belongs on the first factor: `v * v` on its own is `int` arithmetic and overflows at `v >= 46341`, long before the gap range runs out. What carries over: when the cost is convex in each coordinate and the budget is enormous, the optimum is a level set, so binary search the level rather than simulating the spend. The per-unit heap and the binary search express the same greedy; only one of them is indifferent to how large `k` is.