Minimum Sum of Squared Difference

Medium
1392.

Minimum Sum of Squared Difference

Minimum Sum of Squared Difference is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

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.length
  • 1 <= n <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000
  • 0 <= k1, k2 <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k1
 * @param {number} k2
 * @return {number}
 */
var minSumSquareDiff = function(nums1, nums2, k1, k2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • 1 <= n <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000
  • 0 <= k1, k2 <= 10^9

Hints for Minimum Sum of Squared Difference

  1. Hint 1

    A move on nums1[i] or on nums2[i] does the same thing: it shrinks the difference |nums1[i] - nums2[i]| by one. So only k = k1 + k2 matters.

  2. Hint 2

    Squares punish large differences most, so each move should go to the currently largest difference.

  3. Hint 3

    Instead of simulating k moves, binary-search the level T that all differences above it get flattened down to, then spread the leftover moves one apiece among the differences sitting at T.

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

  1. Compute d_i = |nums1[i] - nums2[i]| and k = k1 + k2. If Σ d_i <= k, return 0.
  2. Binary-search the smallest T >= 0 with Σ max(0, d_i - T) <= k. (T >= 1 here, since cutting to 0 would cost more than k.)
  3. Let rem = k - Σ max(0, d_i - T) and c = number of d_i >= T; minimality of T guarantees rem < c.
  4. 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 + k2 can be 2 · 10^9 — keep it in 64-bit in languages with 32-bit int.
  • 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