2333. Minimum Sum of Squared Difference LeetCode Solution

Last updated: February 27, 2025

In this guide, you will get 2333. Minimum Sum of Squared Difference LeetCode Solution with the best time and space complexity. The solution to Minimum Sum of Squared Difference problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Sum of Squared Difference solution in C++
Minimum Sum of Squared Difference solution in Java
Minimum Sum of Squared Difference solution in Python
Additional Resources

2333. Minimum Sum of Squared Difference LeetCode Solution image

Problem Statement of Minimum Sum of Squared Difference

You are given two positive 0-indexed integer arrays nums1 and nums2, both of length n.
The sum of squared difference of arrays nums1 and nums2 is defined as the sum of (nums1[i] – nums2[i])2 for each 0 <= i < n.
You are also given two positive integers k1 and k2. You can modify any of the elements of nums1 by +1 or -1 at most k1 times. Similarly, you can modify any of the elements of nums2 by +1 or -1 at most k2 times.
Return the minimum sum of squared difference after modifying array nums1 at most k1 times and modifying array nums2 at most k2 times.
Note: You are allowed to modify the array elements to become negative integers.

Example 1:

Input: nums1 = [1,2,3,4], nums2 = [2,10,20,19], k1 = 0, k2 = 0
Output: 579
Explanation: The elements in nums1 and nums2 cannot be modified because k1 = 0 and k2 = 0.
The sum of square difference will be: (1 – 2)2 + (2 – 10)2 + (3 – 20)2 + (4 – 19)2 = 579.

Example 2:

Input: nums1 = [1,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1
Output: 43
Explanation: One way to obtain the minimum sum of square difference is:
– Increase nums1[0] once.
– Increase nums2[2] once.
The minimum of the sum of square difference will be:
(2 – 5)2 + (4 – 8)2 + (10 – 7)2 + (12 – 9)2 = 43.
Note that, there are other ways to obtain the minimum of the sum of square difference, but there is no way to obtain a sum smaller than 43.

Constraints:

n == nums1.length == nums2.length
1 <= n <= 105
0 <= nums1[i], nums2[i] <= 105
0 <= k1, k2 <= 109

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

2333. Minimum Sum of Squared Difference LeetCode Solution in C++

class Solution {
 public:
  long long minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1,
                             int k2) {
    const vector<int> diff = getDiff(nums1, nums2);
    int k = k1 + k2;
    if (accumulate(diff.begin(), diff.end(), 0L) <= k)
      return 0;

    unordered_map<int, int> count;
    priority_queue<pair<int, int>> maxHeap;  // (num, freq)

    for (const int d : diff)
      if (d != 0)
        ++count[d];

    for (const auto& [num, freq] : count)
      maxHeap.emplace(num, freq);

    while (k > 0) {
      const auto [maxNum, maxNumFreq] = maxHeap.top();
      maxHeap.pop();
      // Buck decrease in this turn
      const int numDecreased = min(k, maxNumFreq);
      k -= numDecreased;
      if (maxNumFreq > numDecreased)
        maxHeap.emplace(maxNum, maxNumFreq - numDecreased);
      if (!maxHeap.empty() && maxHeap.top().first + 1 == maxNum) {
        const auto [secondMaxNum, secondMaxNumFreq] = maxHeap.top();
        maxHeap.pop();
        maxHeap.emplace(secondMaxNum, secondMaxNumFreq + numDecreased);
      } else if (maxNum > 1) {
        maxHeap.emplace(maxNum - 1, numDecreased);
      }
    }

    long ans = 0;
    while (!maxHeap.empty()) {
      const auto [num, freq] = maxHeap.top();
      maxHeap.pop();
      ans += static_cast<long>(num) * num * freq;
    }

    return ans;
  }

 private:
  vector<int> getDiff(const vector<int>& nums1, const vector<int>& nums2) {
    vector<int> diff;
    for (int i = 0; i < nums1.size(); ++i)
      diff.push_back(abs(nums1[i] - nums2[i]));
    return diff;
  }
};
/* code provided by PROGIEZ */

2333. Minimum Sum of Squared Difference LeetCode Solution in Java

class Solution {
  public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {
    int[] diff = getDiff(nums1, nums2);
    int k = k1 + k2;
    if (Arrays.stream(diff).asLongStream().sum() <= k)
      return 0;

    Map<Integer, Integer> count = new HashMap<>();
    // (num, freq)
    Queue<Pair<Integer, Integer>> maxHeap =
        new PriorityQueue<>(Comparator.comparing(Pair::getKey, Comparator.reverseOrder()));

    for (final int d : diff)
      if (d != 0)
        count.merge(d, 1, Integer::sum);

    for (Map.Entry<Integer, Integer> entry : count.entrySet())
      maxHeap.offer(new Pair<>(entry.getKey(), entry.getValue()));

    while (k > 0) {
      Pair<Integer, Integer> pair = maxHeap.poll();
      final int maxNum = pair.getKey();
      final int maxNumFreq = pair.getValue();
      // Buck decrease in this turn
      final int numDecreased = Math.min(k, maxNumFreq);
      k -= numDecreased;
      if (maxNumFreq > numDecreased)
        maxHeap.offer(new Pair<>(maxNum, maxNumFreq - numDecreased));
      if (!maxHeap.isEmpty() && maxHeap.peek().getKey() + 1 == maxNum) {
        Pair<Integer, Integer> secondNode = maxHeap.poll();
        final int secondMaxNum = secondNode.getKey();
        final int secondMaxNumFreq = secondNode.getValue();
        maxHeap.offer(new Pair<>(secondMaxNum, secondMaxNumFreq + numDecreased));
      } else if (maxNum > 1) {
        maxHeap.offer(new Pair<>(maxNum - 1, numDecreased));
      }
    }

    long ans = 0;
    while (!maxHeap.isEmpty()) {
      Pair<Integer, Integer> pair = maxHeap.poll();
      final int num = pair.getKey();
      final int freq = pair.getValue();
      ans += (long) num * num * freq;
    }

    return ans;
  }

  private int[] getDiff(int[] nums1, int[] nums2) {
    int[] diff = new int[nums1.length];
    for (int i = 0; i < nums1.length; ++i)
      diff[i] = Math.abs(nums1[i] - nums2[i]);
    return diff;
  }
}
// code provided by PROGIEZ

2333. Minimum Sum of Squared Difference LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents