2333. Minimum Sum of Squared Difference

MediumGreedyArrayBinary SearchSortingHeap (Priority Queue)

Problem Description

You have two arrays nums1 and nums2, both containing positive integers and having the same length n. The sum of squared difference between these arrays is calculated by taking the difference between corresponding elements at each position, squaring that difference, and then summing all these squared values. Mathematically, this is: (nums1[0] - nums2[0])² + (nums1[1] - nums2[1])² + ... + (nums1[n-1] - nums2[n-1])².

You're given two additional positive integers k1 and k2 that represent modification budgets:

You can modify elements in nums1 by adding or subtracting 1, up to k1 times total
You can modify elements in nums2 by adding or subtracting 1, up to k2 times total

Each modification operation changes a single element by exactly 1 (either +1 or -1). You can apply multiple modifications to the same element, and elements can become negative after modifications.

Your task is to minimize the sum of squared differences by strategically using your available modifications. Return the minimum possible sum of squared differences after using at most k1 modifications on nums1 and at most k2 modifications on nums2.

For example, if nums1 = [1, 2, 3] and nums2 = [4, 2, 1], the initial differences are [-3, 0, 2] and the sum of squared differences is 9 + 0 + 4 = 13. With modifications, you could reduce these differences to minimize the final result.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is that modifying nums1[i] by +1 or -1, or modifying nums2[i] by +1 or -1, both have the same effect: they change the absolute difference |nums1[i] - nums2[i]| by 1. This means we can combine both modification budgets into a single budget k = k1 + k2 and think about reducing the absolute differences directly.

Since we want to minimize the sum of squared differences, and squaring amplifies larger values more than smaller ones, we should prioritize reducing the largest differences first. For example, reducing a difference from 5 to 4 saves us 25 - 16 = 9 in the squared sum, while reducing from 2 to 1 only saves us 4 - 1 = 3.

The problem then becomes: given an array of absolute differences and k operations, how can we minimize the sum of squares? The greedy approach would be to repeatedly reduce the largest difference by 1, but this could be inefficient for large k.

A more efficient approach uses binary search. We can search for the smallest possible maximum value in the final difference array. The idea is: "What's the smallest value x such that we can make all differences at most x using at most k operations?"

For any candidate value mid, we can calculate how many operations are needed to bring all differences down to at most mid. If this requires more than k operations, we need a larger target value. If it requires at most k operations, we might be able to go even smaller.

Once we find this optimal maximum value, we first bring all differences down to this value. If we still have operations left, we distribute them evenly among the elements at this maximum value, reducing them by 1 each, until we run out of operations. This ensures we're always reducing the largest remaining values, which gives us the optimal result.

Learn more about Greedy, Binary Search, Sorting and Heap (Priority Queue) patterns.

Solution Implementation

1class Solution:
2    def minSumSquareDiff(
3        self, nums1: List[int], nums2: List[int], k1: int, k2: int
4    ) -> int:
5        # Calculate absolute differences between corresponding elements
6        differences = [abs(a - b) for a, b in zip(nums1, nums2)]
7
8        # Total operations available (both k1 and k2 can be used interchangeably)
9        total_operations = k1 + k2
10
11        # If we have enough operations to reduce all differences to zero
12        if sum(differences) <= total_operations:
13            return 0
14
15        max_diff = max(differences)
16
17        # Feasible function: can we reduce all differences to at most 'target'
18        # using at most 'total_operations' operations?
19        def feasible(target):
20            operations_needed = sum(max(diff - target, 0) for diff in differences)
21            return operations_needed <= total_operations
22
23        # Binary search to find the minimum threshold using the template
24        left, right = 0, max_diff - 1
25        first_true_index = max_diff  # Default if no smaller threshold is feasible
26
27        while left <= right:
28            mid = (left + right) // 2
29            if feasible(mid):
30                first_true_index = mid
31                right = mid - 1  # Try to find smaller threshold
32            else:
33                left = mid + 1
34
35        optimal_threshold = first_true_index
36
37        # Reduce all differences to at most the optimal threshold
38        for i, diff in enumerate(differences):
39            operations_used = max(0, diff - optimal_threshold)
40            differences[i] = min(optimal_threshold, diff)
41            total_operations -= operations_used
42
43        # Distribute remaining operations to further reduce values at the threshold
44        # We can only reduce values that are currently at the threshold level
45        for i, diff in enumerate(differences):
46            if total_operations == 0:
47                break
48            if diff == optimal_threshold:
49                total_operations -= 1
50                differences[i] -= 1
51
52        # Calculate and return the sum of squared differences
53        return sum(diff * diff for diff in differences)
54

1class Solution {
2    public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {
3        int n = nums1.length;
4        int[] differences = new int[n];
5        long totalSum = 0;
6        int maxDifference = 0;
7        int totalOperations = k1 + k2;
8
9        // Calculate absolute differences and find the maximum difference
10        for (int i = 0; i < n; i++) {
11            differences[i] = Math.abs(nums1[i] - nums2[i]);
12            totalSum += differences[i];
13            maxDifference = Math.max(maxDifference, differences[i]);
14        }
15
16        // If we can reduce all differences to 0, return 0
17        if (totalSum <= totalOperations) {
18            return 0;
19        }
20
21        // Binary search using the template to find the optimal threshold
22        int left = 0;
23        int right = maxDifference - 1;
24        int firstTrueIndex = maxDifference;  // Default if no smaller threshold is feasible
25
26        while (left <= right) {
27            int mid = left + (right - left) / 2;
28            long operationsNeeded = 0;
29
30            // Calculate operations needed to reduce all values to at most mid
31            for (int value : differences) {
32                operationsNeeded += Math.max(value - mid, 0);
33            }
34
35            if (operationsNeeded <= totalOperations) {
36                // Feasible: can achieve this threshold
37                firstTrueIndex = mid;
38                right = mid - 1;  // Try to find smaller threshold
39            } else {
40                left = mid + 1;
41            }
42        }
43
44        int optimalThreshold = firstTrueIndex;
45
46        // Reduce all differences greater than threshold to the threshold value
47        for (int i = 0; i < n; i++) {
48            totalOperations -= Math.max(0, differences[i] - optimalThreshold);
49            differences[i] = Math.min(differences[i], optimalThreshold);
50        }
51
52        // Use remaining operations to further reduce values at the threshold
53        // This distributes the remaining operations optimally
54        for (int i = 0; i < n && totalOperations > 0; i++) {
55            if (differences[i] == optimalThreshold) {
56                totalOperations--;
57                differences[i]--;
58            }
59        }
60
61        // Calculate the sum of squares of the final differences
62        long sumOfSquares = 0;
63        for (int value : differences) {
64            sumOfSquares += (long) value * value;
65        }
66
67        return sumOfSquares;
68    }
69}
70

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();
7        vector<int> differences(n);
8        ll totalSum = 0;
9        int maxDiff = 0;
10        int totalOperations = k1 + k2;
11
12        // Calculate absolute differences and find maximum difference
13        for (int i = 0; i < n; ++i) {
14            differences[i] = abs(nums1[i] - nums2[i]);
15            totalSum += differences[i];
16            maxDiff = max(maxDiff, differences[i]);
17        }
18
19        // If we can reduce all differences to 0, return 0
20        if (totalSum <= totalOperations) {
21            return 0;
22        }
23
24        // Binary search using the template to find the optimal threshold
25        int left = 0;
26        int right = maxDiff - 1;
27        int firstTrueIndex = maxDiff;  // Default if no smaller threshold is feasible
28
29        while (left <= right) {
30            int mid = left + (right - left) / 2;
31            ll operationsNeeded = 0;
32
33            // Calculate operations needed to reduce all values to mid
34            for (int val : differences) {
35                operationsNeeded += max(val - mid, 0);
36            }
37
38            if (operationsNeeded <= totalOperations) {
39                // Feasible: can achieve this threshold
40                firstTrueIndex = mid;
41                right = mid - 1;  // Try to find smaller threshold
42            } else {
43                left = mid + 1;
44            }
45        }
46
47        int optimalThreshold = firstTrueIndex;
48
49        // Reduce all differences greater than threshold to threshold
50        for (int i = 0; i < n; ++i) {
51            int reduction = max(0, differences[i] - optimalThreshold);
52            totalOperations -= reduction;
53            differences[i] = min(differences[i], optimalThreshold);
54        }
55
56        // Use remaining operations to further reduce values at threshold
57        // This distributes remaining operations evenly
58        for (int i = 0; i < n && totalOperations > 0; ++i) {
59            if (differences[i] == optimalThreshold) {
60                --totalOperations;
61                --differences[i];
62            }
63        }
64
65        // Calculate the sum of squares of final differences
66        ll result = 0;
67        for (int val : differences) {
68            result += 1ll * val * val;
69        }
70
71        return result;
72    }
73};
74

1type ll = number;
2
3function minSumSquareDiff(nums1: number[], nums2: number[], k1: number, k2: number): number {
4    const n: number = nums1.length;
5    const differences: number[] = new Array(n);
6    let totalSum: ll = 0;
7    let maxDiff: number = 0;
8    let totalOperations: number = k1 + k2;
9
10    // Calculate absolute differences and find maximum difference
11    for (let i = 0; i < n; i++) {
12        differences[i] = Math.abs(nums1[i] - nums2[i]);
13        totalSum += differences[i];
14        maxDiff = Math.max(maxDiff, differences[i]);
15    }
16
17    // If we can reduce all differences to 0, return 0
18    if (totalSum <= totalOperations) {
19        return 0;
20    }
21
22    // Feasible function: can we reduce all differences to at most 'target'?
23    const feasible = (target: number): boolean => {
24        let operationsNeeded: ll = 0;
25        for (const val of differences) {
26            operationsNeeded += Math.max(val - target, 0);
27        }
28        return operationsNeeded <= totalOperations;
29    };
30
31    // Binary search using the template to find the optimal threshold
32    let left: number = 0;
33    let right: number = maxDiff - 1;
34    let firstTrueIndex: number = maxDiff;  // Default if no smaller threshold is feasible
35
36    while (left <= right) {
37        const mid: number = Math.floor((left + right) / 2);
38        if (feasible(mid)) {
39            firstTrueIndex = mid;
40            right = mid - 1;  // Try to find smaller threshold
41        } else {
42            left = mid + 1;
43        }
44    }
45
46    const optimalThreshold: number = firstTrueIndex;
47
48    // Reduce all differences greater than threshold to threshold
49    for (let i = 0; i < n; i++) {
50        const reduction: number = Math.max(0, differences[i] - optimalThreshold);
51        totalOperations -= reduction;
52        differences[i] = Math.min(differences[i], optimalThreshold);
53    }
54
55    // Use remaining operations to further reduce values at threshold
56    // This distributes remaining operations evenly
57    for (let i = 0; i < n && totalOperations > 0; i++) {
58        if (differences[i] === optimalThreshold) {
59            totalOperations--;
60            differences[i]--;
61        }
62    }
63
64    // Calculate the sum of squares of final differences
65    let result: ll = 0;
66    for (const val of differences) {
67        result += val * val;
68    }
69
70    return result;
71}
72

Solution Approach

First, we calculate the absolute differences between corresponding elements and store them in array d. Since modifying either array has the same effect on the difference, we combine both budgets: k = k1 + k2.

If the sum of all differences is less than or equal to k, we can reduce all differences to 0, so we return 0 immediately.

Binary Search for Optimal Maximum:

We use binary search to find the smallest possible maximum value that all differences can be reduced to within our budget. The search range is from 0 to max(d) - 1.

We define our feasible function: feasible(mid) = true if we can reduce all differences to at most mid using at most k operations. This means sum(max(v - mid, 0) for v in d) <= k.

Using the standard binary search template with first_true_index:

left, right = 0, max(differences) - 1
first_true_index = max(differences)  # Default if no smaller threshold is feasible

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):  # Can we achieve threshold mid?
        first_true_index = mid
        right = mid - 1  # Try to find smaller threshold
    else:
        left = mid + 1

Apply the Reductions:

After finding the optimal maximum value first_true_index, we first reduce all differences to at most this value:

for i, v in enumerate(d):
    d[i] = min(first_true_index, v)
    k -= max(0, v - first_true_index)

This step uses up some of our operations, and k now contains the remaining operations.

Distribute Remaining Operations:

If we still have operations left (k > 0), we need to distribute them among the elements that are currently at the maximum value. We iterate through the array and reduce each element at value first_true_index by 1, one at a time, until we run out of operations:

for i, v in enumerate(d):
    if k == 0:
        break
    if v == first_true_index:
        k -= 1
        d[i] -= 1

This ensures we're always reducing the largest values first, which is optimal for minimizing the sum of squares.

Calculate Final Result:

Finally, we calculate and return the sum of squared differences: sum(v * v for v in d).

The time complexity is O(n log(max(d))) for the binary search, where each check takes O(n) time. The space complexity is O(n) for storing the differences array.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example with nums1 = [10, 10, 10], nums2 = [3, 3, 3], k1 = 6, and k2 = 6.

Step 1: Calculate initial differences

Differences: d = [|10-3|, |10-3|, |10-3|] = [7, 7, 7]
Combined budget: k = k1 + k2 = 12
Initial sum of squared differences: 7² + 7² + 7² = 147

Step 2: Check if we can reduce everything to 0

Sum of differences: 7 + 7 + 7 = 21
Since 21 > 12, we cannot reduce all differences to 0

Step 3: Binary search for optimal maximum using template

Initialize: left = 0, right = 6, first_true_index = 7 (max difference as default)
Feasible function: feasible(mid) = can we reduce all values to at most mid using ≤ 12 operations?

Iteration 1: left = 0, right = 6

mid = (0 + 6) // 2 = 3
Operations needed: (7-3) + (7-3) + (7-3) = 12 ≤ 12 → feasible!
Update first_true_index = 3, right = mid - 1 = 2

Iteration 2: left = 0, right = 2

mid = (0 + 2) // 2 = 1
Operations needed: (7-1) + (7-1) + (7-1) = 18 > 12 → not feasible
Update left = mid + 1 = 2

Iteration 3: left = 2, right = 2

mid = (2 + 2) // 2 = 2
Operations needed: (7-2) + (7-2) + (7-2) = 15 > 12 → not feasible
Update left = mid + 1 = 3

Iteration 4: left = 3, right = 2

left > right, loop terminates
Result: first_true_index = 3

Step 4: Apply reductions to reach maximum of 3

Reduce each difference from 7 to 3: d = [3, 3, 3]
Operations used: (7-3) + (7-3) + (7-3) = 12
Remaining operations: k = 12 - 12 = 0

Step 5: Distribute remaining operations

Since k = 0, no additional operations to distribute

Step 6: Calculate final result

Final differences: [3, 3, 3]
Sum of squared differences: 3² + 3² + 3² = 27

The algorithm successfully reduced the sum of squared differences from 147 to 27 by strategically using all 12 available operations to bring each difference down to 3.

Time and Space Complexity

Time Complexity: O(n * log(max(d)))

The algorithm breaks down as follows:

Creating the difference array d: O(n) where n is the length of nums1/nums2
Finding the sum of d: O(n)
Binary search with left and right bounds: O(log(max(d))) iterations
- Within each binary search iteration, calculating sum(max(v - mid, 0) for v in d): O(n)
- Total for binary search: O(n * log(max(d)))
First loop to update d with left value: O(n)
Second loop to decrement values equal to left: O(n) in worst case
Final sum calculation: O(n)

The dominant term is O(n * log(max(d))) from the binary search phase.

Space Complexity: O(n)

The space usage includes:

Array d storing the absolute differences: O(n)
Other variables (k, left, right, mid): O(1)

The algorithm uses O(n) extra space for storing the differences array, with no additional data structures that scale with input size.

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

Common Pitfalls

1. Using Wrong Binary Search Template

The Pitfall: Using while left < right with right = mid instead of the standard template with while left <= right, first_true_index, and right = mid - 1.

Why It's Wrong: Different binary search variants behave differently at boundaries. Using inconsistent patterns makes code harder to reason about and more prone to off-by-one errors.

The Solution: Use the standard template consistently:

left, right = 0, max_diff - 1
first_true_index = max_diff  # Default value

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

2. Incorrect Distribution of Remaining Operations

The Pitfall: After reducing all differences to the optimal threshold, there may be leftover operations. A common mistake is to arbitrarily distribute these operations or apply them all to a single element, which doesn't minimize the sum of squares optimally.

Why It's Wrong: Consider differences [3, 3, 3] with 2 remaining operations. If you reduce only the first element to get [1, 3, 3], the sum of squares is 1 + 9 + 9 = 19. But if you reduce two elements by 1 each to get [2, 2, 3], the sum is 4 + 4 + 9 = 17, which is better.

The Solution: Always reduce the largest values first, one at a time. In the code, this is handled by:

for i, diff in enumerate(differences):
    if total_operations == 0:
        break
    if diff == optimal_threshold:
        total_operations -= 1
        differences[i] -= 1

This ensures we're spreading the reductions across multiple elements at the maximum value, rather than concentrating them.

3. Not Handling the Case Where All Differences Can Be Reduced to Zero

The Pitfall: Forgetting to check if sum(differences) <= total_operations at the beginning, leading to unnecessary computation and potentially incorrect results.

Why It's Wrong: If you have enough operations to eliminate all differences completely, the minimum sum of squares is always 0. Without this check, the binary search might find a non-zero threshold, and you'd still have unused operations after the algorithm completes.

The Solution: Always check this condition first:

if sum(differences) <= total_operations:
    return 0

This provides an early exit for cases where complete elimination is possible, improving both correctness and efficiency.

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

Which type of traversal does breadth first search do?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know