2333. Minimum Sum of Squared Difference


Problem Description

The problem provides two arrays nums1 and nums2 of the same length n, and asks for the minimum sum of squared difference after you can modify the elements of these arrays a certain number of times. The sum of squared difference is calculated as the sum of (nums1[i] - nums2[i])^2 for each index i in the arrays. The additional twist to this problem is that you are allowed to increment or decrement the elements of nums1 up to k1 times in total, and similarly for the elements of nums2 up to k2 times.

One key aspect to note is that the modifications to the array elements don't need to be spread out evenly; they can be applied to any element any number of times, so long as the total number of modifications doesn't exceed k1 or k2 respectively. It's also mentioned that the elements are allowed to become negative due to these modifications.

The goal is to find the strategy of modifying the elements of both arrays that results in the minimum sum of squared differences. This is an optimization problem that requires a bit of strategic thinking, as the modifications should be applied in a way to reduce the largest differences first, as they contribute more to the sum of squared differences.

Intuition

A direct approach would be to try to modify the elements where the differences are the greatest, as reducing larger differences has a higher impact on lowering the sum of squared differences than reducing smaller differences. However, attempting all possibilities would be computationally infeasible for large arrays.

The intuition behind the solution is to determine a threshold such that we want to reduce every difference above this threshold to at least that value by using our available modifications (the combined k1 and k2 modifications). Once this is done, if we still have remaining modifications, we can further reduce some of these distances by one more.

The solution uses a binary search over the possible values of the threshold, which helps to quickly hone in on the smallest threshold where the total modifications needed to bring all differences down to that threshold or less does not exceed the total available k1 + k2 modifications. Once the threshold is determined, the distances are reduced accordingly, and if there are any modifications left, they are applied to the distances at the threshold until we run out of modifications.

To prove that this approach is correct, we can rely on the idea that for a non-negative integer x, the function f(x) = x*x is strictly increasing for x ≥ 0. Because our distances are absolute values, we know they are non-negative, so reducing larger distances first minimizes the overall sum of squared differences quicker than reducing smaller distances.

Learn more about Math, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The solution code primarily uses binary search to find the threshold and then a greedy approach to apply the remaining modifications. Below, I'll walk through the significant parts of the implementation:

  1. Calculating the initial differences: The first step is to compute the absolute differences between corresponding elements of nums1 and nums2. This is done with a list comprehension:

    1d = [abs(a - b) for a, b in zip(nums1, nums2)]

    The resulting d list contains the differences, which we are looking to minimize.

  2. Combining the modifications: The total number of modifications available is the sum of k1 and k2, since there's no requirement that a specific number of modifications have to be applied to either nums1 or nums2. This is simply:

    1k = k1 + k2

    If the sum of all differences in d is less than or equal to k, we can reduce all differences to zero:

    1if sum(d) <= k:
    2    return 0
  3. Using binary search to find the threshold: We perform binary search over the potential values of our threshold. The left and right point to the range within which we search.

    1left, right = 0, max(d)
    2while left < right:
    3    mid = (left + right) >> 1
    4    if sum(max(v - mid, 0) for v in d) <= k:
    5        right = mid
    6    else:
    7        left = mid + 1

    We keep doing this until left and right converge to the smallest threshold. The sum(max(v - mid, 0) for v in d) calculates how many modifications are needed to reduce all differences greater than mid to at least mid. If this sum is less than or equal to k, then mid is a valid threshold, and we continue searching to the left (lowering the possible threshold). Otherwise, we search to the right (increasing the threshold).

  4. Applying reductions up to the threshold: Next, we reduce the differences to the threshold, and update the number of residual modifications (k), since not all of them might be needed to reach the threshold.

    1for i, v in enumerate(d):
    2    d[i] = min(left, v)
    3    k -= max(0, v - left)
  5. Using residual modifications: If any modifications are left (k > 0), we apply them to further reduce the differences that are equal to the threshold. This decreases the value by 1 for as many elements as possible, given the residual k.

    1for i, v in enumerate(d):
    2    if k == 0:
    3        break
    4    if v == left:
    5        k -= 1
    6        d[i] -= 1
  6. Calculating the final sum: Lastly, after we have applied all modifications, we compute the final sum of squared differences.

    1return sum(v * v for v in d)

The algorithm effectively combines binary search to find a suitable threshold with a greedy approach to apply any remaining modifications. The use of binary search ensures that the solution runs efficiently even on large arrays, while the greedy application of modifications ensures that the total sum of squared differences is minimized.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many ways can you arrange the three letters A, B and C?

Example Walkthrough

Let's consider two small arrays nums1 = [1, 4, 6], nums2 = [5, 3, 2] and k1 = 3, k2 = 2. We'll use these arrays to illustrate the solution approach described.

  1. Calculating the initial differences: We first calculate the absolute differences between elements of the two arrays:

    1d = [abs(1 - 5), abs(4 - 3), abs(6 - 2)]
    2d = [4, 1, 4]
  2. Combining the modifications: The total modifications k is the sum of k1 and k2:

    1k = k1 + k2 = 3 + 2 = 5

    Since sum(d) = 4 + 1 + 4 = 9 is not less than or equal to k, we cannot reduce all differences to zero, so we move on to the next step.

  3. Using binary search to find the threshold: We use binary search to find the value up to which we want to reduce our differences. Our array d has differences ranging from 1 to 4, so the left is set to 0 and right is set to 4, the maximum value in d. During the binary search, we find that a threshold of 2 (the mid-value in one of the iterations) requires a total of 2+0+2=4 modifications, which is less than k. We can't go lower because a threshold of 1 would require 3+0+3=6 modifications, which is more than k. So, we set our threshold left to 2.

  4. Applying reductions up to the threshold: We then apply modifications to reduce all differences greater than the threshold down to the threshold:

    1for each element v in d:
    2if v > 2:
    3    k -= (v - 2) // reductions
    4d = [min(v, 2) for v in d]
    5After the loop, we have:
    6d = [2, 1, 2]
    7and `k` is updated to 5 - 4 = 1 (since we made 4 modifications total).
    8
  5. Using residual modifications: Now we have 1 modification left (k = 1). We apply it to one of the elements that are at the threshold:

    1d[0] -= 1 if k > 0
    2d = [1, 1, 2]   // here we decrement the first element from 2 to 1

    We have now used all our modifications.

  6. Calculating the final sum: The final sum of squared differences is computed as:

    1sum = (1 * 1) + (1 * 1) + (2 * 2) = 1 + 1 + 4 = 6

Thus, the minimum sum of squared differences after using all the modifications is 6.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minSumSquareDiff(self, nums1: List[int], nums2: List[int], k1: int, k2: int) -> int:
5        # Calculate the absolute differences between the elements of two arrays
6        diff = [abs(a - b) for a, b in zip(nums1, nums2)]
7        # Total number of operations available
8        total_operations = k1 + k2
9      
10        # If the sum of differences is less than or equal to the total operations,
11        # then we can make the square difference zero
12        if sum(diff) <= total_operations:
13            return 0
14
15        # Binary search for the smallest value x such that
16        # the sum of the differences decreased by x is less than or equal to k
17        left, right = 0, max(diff)
18        while left < right:
19            mid = (left + right) // 2
20            if sum(max(value - mid, 0) for value in diff) <= total_operations:
21                right = mid
22            else:
23                left = mid + 1
24      
25        # Decrease each element in diff by left, but not below zero.
26        # Apply the remaining operations if there are any.
27        for i in range(len(diff)):
28            diff[i] = min(left, diff[i])
29            total_operations -= max(0, diff[i] - left)
30
31        # If there are still operations left, use them to reduce some
32        # of the elements equal to `left` by 1.
33        for i, value in enumerate(diff):
34            if total_operations == 0:
35                break
36            if value == left:
37                total_operations -= 1
38                diff[i] -= 1
39      
40        # Calculate the sum of squares of the modified difference array
41        return sum(value ** 2 for value in diff)
42
1class Solution {
2
3    public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {
4        int length = nums1.length;
5        int[] differences = new int[length];
6        long sumDifferences = 0;
7        int maxDifference = 0;
8        int totalOperationsAllowed = k1 + k2;
9
10        // Calculate the absolute differences of each pair and find the max difference.
11        for (int i = 0; i < length; ++i) {
12            differences[i] = Math.abs(nums1[i] - nums2[i]);
13            sumDifferences += differences[i];
14            maxDifference = Math.max(maxDifference, differences[i]);
15        }
16
17        // If the sum of differences is less than the total number of operations allowed,
18        // we can make all pairs equal.
19        if (sumDifferences <= totalOperationsAllowed) {
20            return 0;
21        }
22
23        // Perform a binary search on the value of the difference.
24        int left = 0, right = maxDifference;
25        while (left < right) {
26            int mid = (left + right) / 2;
27            long operationsNeeded = 0;
28            for (int diffValue : differences) {
29                operationsNeeded += Math.max(diffValue - mid, 0);
30            }
31            if (operationsNeeded <= totalOperationsAllowed) {
32                right = mid;
33            } else {
34                left = mid + 1;
35            }
36        }
37
38        // Reduce each difference by at least 'left' and count remaining operations.
39        for (int i = 0; i < length; ++i) {
40            totalOperationsAllowed -= Math.max(0, differences[i] - left);
41            differences[i] = Math.min(differences[i], left);
42        }
43
44        // Use any leftover operations to decrease differences of 'left' by 1.
45        for (int i = 0; i < length && totalOperationsAllowed > 0; ++i) {
46            if (differences[i] == left) {
47                totalOperationsAllowed--;
48                differences[i]--;
49            }
50        }
51
52        // Calculate the final sum of squares of differences.
53        long ans = 0;
54        for (int difference : differences) {
55            ans += (long) difference * difference;
56        }
57
58        return ans;
59    }
60
61}
62
1using ll = long long;
2
3class Solution {
4public:
5    long long minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2) {
6        int n = nums1.size(); // Size of arrays
7        vector<int> differences(n); // Vector to store absolute difference between nums1 and nums2
8        ll sumOfDifferences = 0; // Sum of differences
9        int maxDifference = 0; // Maximum difference value
10        int operations = k1 + k2; // Total number of operations we can perform
11
12        // Calculate the differences and total sum of differences
13        for (int i = 0; i < n; ++i) {
14            differences[i] = abs(nums1[i] - nums2[i]);
15            sumOfDifferences += differences[i];
16            maxDifference = max(maxDifference, differences[i]);
17        }
18
19        // If we can make all differences to be zero, return 0
20        if (sumOfDifferences <= operations) return 0;
21
22        // Binary search to find the smallest maximum difference after operations
23        int left = 0, right = maxDifference;
24        while (left < right) {
25            int mid = (left + right) >> 1;
26            ll requiredOperations = 0;
27            for (int difference : differences) {
28                requiredOperations += max(difference - mid, 0);
29            }
30            // Adjust search space based on the total operations needed
31            if (requiredOperations <= operations)
32                right = mid;
33            else
34                left = mid + 1;
35        }
36
37        // Apply the determined operations to reduce differences
38        for (int i = 0; i < n; ++i) {
39            operations -= max(0, differences[i] - left);
40            differences[i] = min(differences[i], left);
41        }
42
43        // If there are operations left, further reduce the biggest differences
44        for (int i = 0; i < n && operations; ++i) {
45            if (differences[i] == left) {
46                --operations;
47                --differences[i];
48            }
49        }
50
51        // Calculate the final sum of squared differences
52        ll squaredDifferenceSum = 0;
53        for (int value : differences) squaredDifferenceSum += static_cast<ll>(value) * value;
54
55        return squaredDifferenceSum;
56    }
57};
58
1type int = number;
2type ll = number;
3
4// Given two arrays nums1 and nums2 and a total number of operations that can be performed, k, this function returns
5// the minimum sum of the squared difference between elements of the arrays after performing at most k operations.
6function minSumSquareDiff(nums1: int[], nums2: int[], k1: int, k2: int): ll {
7    const n: int = nums1.length; // Size of arrays
8    const differences: int[] = new Array(n); // Array to store absolute difference between nums1 and nums2 elements
9    let sumOfDifferences: ll = 0; // Sum of absolute differences
10    let maxDifference: int = 0; // Maximum absolute difference value
11    let operations: int = k1 + k2; // Total number of operations we can perform
12
13    // Calculate the absolute differences and the sum of absolute differences
14    for (let i = 0; i < n; ++i) {
15        differences[i] = Math.abs(nums1[i] - nums2[i]);
16        sumOfDifferences += differences[i];
17        maxDifference = Math.max(maxDifference, differences[i]);
18    }
19
20    // If we can reduce all differences to zero using the operations provided, return 0
21    if (sumOfDifferences <= operations) return 0;
22
23    // Binary search to find the smallest maximum difference after performing the operations
24    let left: int = 0, right: int = maxDifference;
25    while (left < right) {
26        const mid: int = Math.floor((left + right) / 2);
27        let requiredOperations: ll = 0;
28        for (const difference of differences) {
29            requiredOperations += Math.max(difference - mid, 0);
30        }
31      
32        // Adjust the search range based on the number of operations that would be required
33        if (requiredOperations <= operations)
34            right = mid;
35        else
36            left = mid + 1;
37    }
38
39    // Reduce the differences by the number of operations determined
40    for (let i = 0; i < n; ++i) {
41        if (differences[i] > left) {
42            operations -= (differences[i] - left);
43            differences[i] = left;
44        }
45    }
46
47    // Distribute the remaining operations, if any, to further reduce differences
48    for (let i = 0; i < n && operations > 0; ++i) {
49        if (differences[i] === left) {
50            --operations;
51            --differences[i];
52        }
53    }
54
55    // Compute the final sum of squared differences
56    let squaredDifferenceSum: ll = 0;
57    for (const value of differences) {
58        squaredDifferenceSum += value * value;
59    }
60
61    return squaredDifferenceSum;
62}
63

Time and Space Complexity

The given Python code aims to minimize the sum of the squared differences of elements from two arrays nums1 and nums2 after making at most k1 decreases and k2 increases to the elements of the two arrays.

Time Complexity

The time complexity of the code is determined by several factors:

  1. Calculating differences: O(n) where n is the length of input arrays.
  2. Summing the differences: O(n).
  3. Performing a binary search for the optimal maximum difference after operations, which runs in O(log(max(d))) where max(d) is the maximum absolute difference.
  4. Inside each binary search iteration, the sum of the max modified differences is calculated, which is O(n).
  5. Iterating through d to reduce the values by left: O(n).

Combining these, the binary search's complexity of O(log(max(d))) multiplies with the linear passes which are O(n), leading to a final time complexity of O(n*log(max(d))).

Space Complexity

The space complexity is determined by the extra space used, which in this case is:

  1. The list d where the absolute differences are stored: O(n) space.

No other significant auxiliary space is used (ignoring the space used for the function call stack), so the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄