Minimum Sum of Squared Difference

#380 Most AskedMedium

Minimum Sum of Squared Difference #380 Most Asked

Medium

Microsoft

29 views

Topics:

ArraysGreedy AlgorithmsBinary SearchStacksDynamic Programming

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])² 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 - 10)²+ (3 - 20)²+ (4 - 19)² = 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)²+ (4 - 8)²+ (10 - 7)²+ (12 - 9)² = 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 <= 10⁵
0 <= nums1[i], nums2[i] <= 10⁵
0 <= k1, k2 <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer values within the input arrays?
Can the input arrays `nums1` and `nums2` be empty, or have different lengths?
Is the integer `k` guaranteed to be non-negative?
If after applying `k` operations, the minimum sum of squared difference is 0, is that a valid result, and can I return 0 immediately?
Are we looking for integer arithmetic only? In other words, is it possible to have a non-integer number of operations applied to minimize the difference? (e.g., partially incrementing/decrementing a value).

Brute Force Solution

Approach

The goal is to make two lists of numbers as similar as possible by making changes to the numbers in those lists. The brute force method tries every single possible change we can make to the lists and then checks how close the lists are.

Here's how the algorithm would work step-by-step:

Imagine we can change the first number in the first list to any possible value within the allowed range.
Then, consider changing the second number in the first list to any possible value, and so on, until we've tried all possible changes to the first list using our allowed moves.
After changing all the numbers, we need to do this process for the second list.
For every single combination of changes we made to both lists, we calculate how different they are from each other, using a specific formula (sum of squared differences).
After trying every possible change to both lists, we compare all of the 'difference' scores we got.
The changes that resulted in the smallest 'difference' score is the best way to change the numbers to make them as similar as possible.

Code Implementation

def minimum_sum_of_squared_difference_brute_force(
    first_list,
    second_list,
    number_of_moves1,
    number_of_moves2,
):
    minimum_sum_of_squared_differences = float('inf')
    length_of_list = len(first_list)

    # Iterate through all possible move combinations.
    for i in range(-number_of_moves1, number_of_moves1 + 1):
        for j in range(-number_of_moves1, number_of_moves1 + 1):
            for k in range(-number_of_moves2, number_of_moves2 + 1):
                for l in range(-number_of_moves2, number_of_moves2 + 1):
                    if abs(i) + abs(j) > number_of_moves1 or abs(k) + abs(l) > number_of_moves2:
                        continue

                    # Create copies to avoid modifying original lists.
                    temp_first_list = first_list[:]
                    temp_second_list = second_list[:]
                    temp_first_list[0] += i
                    temp_first_list[1] += j
                    temp_second_list[0] += k
                    temp_second_list[1] += l

                    current_sum_of_squared_differences = 0

                    # Calculate sum of squared differences.
                    for index in range(length_of_list):
                        difference = temp_first_list[index] - temp_second_list[index]
                        current_sum_of_squared_differences += difference * difference

                    # Update the minimum if needed.
                    minimum_sum_of_squared_differences = min(
                        minimum_sum_of_squared_differences,
                        current_sum_of_squared_differences,
                    )

    return minimum_sum_of_squared_differences

Big(O) Analysis

Time Complexity

O((range)^(moves1 + moves2) * n) – The brute force approach explores every possible combination of changes to both lists. For each list, every number can be changed within a given range, and we exhaust all possible moves. If the range of possible values is 'range', and we have 'moves1' and 'moves2' moves for the first and second lists respectively, the number of combinations explodes to (range)^(moves1 + moves2). For each such combination, we iterate through the n elements to calculate the sum of squared differences. Therefore, the total time complexity is O((range)^(moves1 + moves2) * n).

Space Complexity

O(1) – The brute force approach described iterates through all possible changes to the numbers in both lists. However, it doesn't explicitly mention storing all the intermediate 'difference' scores or keeping track of every single combination of changes in a data structure. The explanation focuses on trying changes and comparing 'difference' scores, implying that only the minimum difference and possibly the corresponding changes are stored at any given time. Therefore, the auxiliary space used consists of a few variables to track the current changes being tried and the minimum difference found so far, which is constant regardless of the size of the input lists. Thus, the space complexity is O(1).

Optimal Solution

Approach

To minimize the sum of squared differences, we want to make the two sets of numbers as similar as possible. The core idea is to repeatedly find the biggest differences and reduce them, using available 'moves' wisely to have the largest impact on reducing the overall sum.

Here's how the algorithm would work step-by-step:

Find the pairs of numbers that have the largest differences between them.
Prioritize reducing the largest differences first because reducing a larger difference contributes much more to lowering the sum of squared differences than reducing a smaller one.
For each 'move' available, decide whether to increase a number from the first set or decrease a number from the second set, always targeting the pair with the biggest difference to make them closer.
Repeat this process of finding the largest difference and using a 'move' to reduce it, until all the 'moves' are used up.
After using all the 'moves', calculate the sum of the squared differences between the two sets of numbers. This will be the minimum possible sum achievable.

Code Implementation

def minimum_sum_square_difference(first_array, second_array, k):
    array_length = len(first_array)
    absolute_differences = [abs(first_array[i] - second_array[i]) for i in range(array_length)]

    for _ in range(k):
        max_difference_index = absolute_differences.index(max(absolute_differences))

        # Prioritize reducing the largest difference.
        if first_array[max_difference_index] > second_array[max_difference_index]:
            first_array[max_difference_index] -= 1
        else:
            first_array[max_difference_index] += 1

        absolute_differences[max_difference_index] = abs(first_array[max_difference_index] - second_array[max_difference_index])

    sum_of_squared_differences = 0
    for i in range(array_length):

        # Minimize the sum after using all moves.
        sum_of_squared_differences += (first_array[i] - second_array[i]) ** 2

    return sum_of_squared_differences

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm iterates up to 'moves' times, where 'moves' can potentially be a large value related to the size of the input arrays. In each iteration, it needs to identify the pair with the maximum difference. A naive approach to find the maximum difference would be O(n) in each iteration. However, a more efficient approach involves using a heap (priority queue) to store the differences and efficiently find/update the maximum difference. Building the initial heap takes O(n) time. Then, for each move, extracting the maximum difference from the heap takes O(log n) time, and updating the heap after adjusting the numbers takes O(log n) time. Since this heap operation happens for each 'move' (k) and in the worst case k could approach a function of n, the overall complexity can be seen as driven by the heap updates. Assuming 'moves' (k) is O(n), the time complexity becomes O(n log n). After the moves are exhausted, calculating the final sum of squared differences takes O(n). Therefore, the dominant factor is the heap operations performed 'moves' times, leading to a total time complexity of O(n log n).

Space Complexity

O(1) – The algorithm, as described, operates primarily in-place or uses a constant number of extra variables. It iteratively finds the maximum difference and adjusts values, without creating auxiliary data structures that scale with the input size N (where N is the number of elements in each set). The 'moves' variable and any temporary variables used for comparisons do not depend on N. Therefore, the auxiliary space remains constant, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Empty arrays: nums1 or nums2 are null or empty	Return 0 immediately since the sum of squared differences is zero with no elements.
Arrays of different lengths: nums1 and nums2 have different sizes	Return -1 indicating invalid input, as element-wise comparison is impossible.
Large array sizes that might cause integer overflow in intermediate calculations	Use long data type for intermediate squared differences to prevent potential integer overflow.
k (the modification count) is greater than or equal to the sum of absolute differences	Clamp k to sum of differences; further modifications do not reduce the sum of squared differences.
All elements in nums1 and nums2 are identical	The initial sum of squared differences is zero, and any modifications will only increase it; so, we choose best possible change.
nums1 and nums2 contain very large positive or negative numbers	Handle potential integer overflow during difference calculation by using long data types.
k is zero; no modifications are allowed.	Return the initial sum of squared differences without any changes.
Arrays containing only zero values	Calculate initial difference and apply modifications as appropriate to reduce overall sum of squares.

Empty arrays: nums1 or nums2 are null or empty

How to Handle:

Return 0 immediately since the sum of squared differences is zero with no elements.

Arrays of different lengths: nums1 and nums2 have different sizes

How to Handle:

Return -1 indicating invalid input, as element-wise comparison is impossible.

Large array sizes that might cause integer overflow in intermediate calculations

How to Handle:

Use long data type for intermediate squared differences to prevent potential integer overflow.

k (the modification count) is greater than or equal to the sum of absolute differences

How to Handle:

Clamp k to sum of differences; further modifications do not reduce the sum of squared differences.

All elements in nums1 and nums2 are identical

How to Handle:

The initial sum of squared differences is zero, and any modifications will only increase it; so, we choose best possible change.

nums1 and nums2 contain very large positive or negative numbers

How to Handle:

Handle potential integer overflow during difference calculation by using long data types.

k is zero; no modifications are allowed.

How to Handle:

Return the initial sum of squared differences without any changes.

Arrays containing only zero values

How to Handle:

Calculate initial difference and apply modifications as appropriate to reduce overall sum of squares.