Minimum Sum of Squared Difference — Problem & Solution
Minimum Sum of Squared Difference solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Sum of Squared Difference is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Binary Search
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Two arrays nums1 and nums2 of length n have a sum of squared difference equal to the sum of (nums1[i] - nums2[i])^2 over all i.
You may change elements of nums1 by +1 or -1 at most k1 times in total, and elements of nums2 by +1 or -1 at most k2 times in total. Elements may become negative.
Return the minimum possible sum of squared difference.
CodeKairo bounds: the original allows n and the values up to 10^5, which needs a 64-bit answer. Here n <= 1000 and values are at most 1000, so the answer fits in a 32-bit integer.
Example 1
Input: nums1 = [1,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1
Output: 43
Explanation: The differences are 4, 4, 4, 3; spending both moves on two of the 4s leaves 3, 3, 4, 3 → 9 + 9 + 16 + 9 = 43.
Example 2
Input: nums1 = [7,2], nums2 = [1,2], k1 = 2, k2 = 1
Output: 9
Explanation: Only the first pair differs (by 6); three moves bring it to 3.
Example 3
Input: nums1 = [3,3,3], nums2 = [1,5,3], k1 = 10, k2 = 0
Output: 0
Constraints
n == nums1.length == nums2.length1 <= n <= 10000 <= nums1[i], nums2[i] <= 10000 <= k1, k2 <= 10^9
Hints for Minimum Sum of Squared Difference
Hint 1
A move on
nums1[i]or onnums2[i]does the same thing: it shrinks the difference|nums1[i] - nums2[i]|by one. So onlyk = k1 + k2matters.Hint 2
Squares punish large differences most, so each move should go to the currently largest difference.
Hint 3
Instead of simulating
kmoves, binary-search the levelTthat all differences above it get flattened down to, then spread the leftover moves one apiece among the differences sitting atT.
How to solve Minimum Sum of Squared Difference
Reduce to differences d_i and a combined budget k = k1 + k2. Greedily lowering the largest difference is optimal, and its end result is a water level: every difference above some T is cut to T, with a few of those cut once more to T - 1. Binary search finds T.
Approach
- Compute
d_i = |nums1[i] - nums2[i]|andk = k1 + k2. IfΣ d_i <= k, return 0. - Binary-search the smallest
T >= 0withΣ max(0, d_i - T) <= k. (T >= 1here, since cutting to 0 would cost more thank.) - Let
rem = k - Σ max(0, d_i - T)andc= number ofd_i >= T; minimality ofTguaranteesrem < c. - Answer =
Σ_{d_i < T} d_i^2 + (c - rem) · T^2 + rem · (T - 1)^2.
Why it works
Lowering a difference from x to x - 1 saves 2x - 1, which is largest for the largest x, and the savings available from any one difference only shrink as it is lowered — so the greedy that always lowers a current maximum is optimal (an exchange argument swaps any move on a smaller difference for one on a larger). Running that greedy to completion produces exactly the levelled shape computed above.
Complexity
- Time —
O(n log D) with D the largest difference - Space —
O(n)
Pitfalls
k1 + k2can be 2 · 10^9 — keep it in 64-bit in languages with 32-bitint.- Once every difference is 0 extra moves are wasted (moving past 0 makes it worse), so return 0 when the budget covers the total.
- Leftover moves after the level cut go to differences equal to
T, one each — not all to the same one.
Reference solution
Python
from typing import List
def minSumSquareDiff(nums1: List[int], nums2: List[int], k1: int, k2: int) -> int:
d = [abs(a - b) for a, b in zip(nums1, nums2)]
k = k1 + k2
if sum(d) <= k:
return 0
def cut(T):
return sum(x - T for x in d if x > T)
lo, hi = 0, max(d)
while lo < hi:
mid = (lo + hi) // 2
if cut(mid) <= k:
hi = mid
else:
lo = mid + 1
T = lo
rem = k - cut(T)
at = sum(1 for x in d if x >= T)
rest = sum(x * x for x in d if x < T)
return rest + (at - rem) * T * T + rem * (T - 1) * (T - 1)Java
public static int minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {
int n = nums1.length;
int[] d = new int[n];
long total = 0;
int top = 0;
for (int i = 0; i < n; i++) {
d[i] = Math.abs(nums1[i] - nums2[i]);
total += d[i];
top = Math.max(top, d[i]);
}
long k = (long) k1 + k2;
if (total <= k) return 0;
int lo = 0, hi = top;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (cutCost(d, mid) <= k) hi = mid; else lo = mid + 1;
}
long level = lo;
long rem = k - cutCost(d, lo);
long at = 0, res = 0;
for (int x : d) {
if (x >= level) at++;
else res += (long) x * x;
}
return (int) (res + (at - rem) * level * level + rem * (level - 1) * (level - 1));
}
static long cutCost(int[] d, int T) {
long s = 0;
for (int x : d) if (x > T) s += x - T;
return s;
}C++
long long cutCost(const vector<int>& d, int T) {
long long s = 0;
for (int x : d) if (x > T) s += x - T;
return s;
}
int minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2) {
int n = nums1.size();
vector<int> d(n);
long long total = 0;
int top = 0;
for (int i = 0; i < n; i++) {
d[i] = abs(nums1[i] - nums2[i]);
total += d[i];
top = max(top, d[i]);
}
long long k = (long long)k1 + k2;
if (total <= k) return 0;
int lo = 0, hi = top;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (cutCost(d, mid) <= k) hi = mid; else lo = mid + 1;
}
long long level = lo;
long long rem = k - cutCost(d, lo);
long long at = 0, res = 0;
for (int x : d) {
if (x >= level) at++;
else res += (long long)x * x;
}
return (int)(res + (at - rem) * level * level + rem * (level - 1) * (level - 1));
}JavaScript
var minSumSquareDiff = function(nums1, nums2, k1, k2) {
var n = nums1.length;
var d = [], total = 0, top = 0;
for (var i = 0; i < n; i++) {
var x = Math.abs(nums1[i] - nums2[i]);
d.push(x);
total += x;
if (x > top) top = x;
}
var k = k1 + k2;
if (total <= k) return 0;
var cut = function(T) {
var s = 0;
for (var j = 0; j < n; j++) if (d[j] > T) s += d[j] - T;
return s;
};
var lo = 0, hi = top;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (cut(mid) <= k) hi = mid; else lo = mid + 1;
}
var level = lo;
var rem = k - cut(level);
var at = 0, res = 0;
for (var t = 0; t < n; t++) {
if (d[t] >= level) at++;
else res += d[t] * d[t];
}
return res + (at - rem) * level * level + rem * (level - 1) * (level - 1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms