We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Sum of Squared Difference

Number: 2418

Difficulty: Medium

Paid? No

Companies: Microsoft, Amazon, Uber

Problem Description

Given two integer arrays nums1 and nums2 of equal length, and two integers k1 and k2 representing the maximum number of operations allowed on nums1 and nums2 respectively, an operation being an increment or decrement by one, the objective is to minimize the sum of squared differences between corresponding elements of the two arrays. The sum of squared difference is defined as Σ (nums1[i] - nums2[i])².

Key Insights

  • The absolute difference at each index, diff[i] = |nums1[i] - nums2[i]|, is the target for reduction.
  • The total number of available operations is k = k1 + k2; each operation reduces one unit from some diff.
  • Optimal strategy is to greedily reduce the largest differences first since reducing a larger diff by one typically produces more benefit in terms of decreasing its square.
  • Using a frequency “bucket” that counts how many elements have each possible difference (from 0 up to maxDiff) enables efficient simulation of operations.

Space and Time Complexity

Time Complexity: O(n + D) where n is the length of the arrays and D is the maximum difference (up to 10^5).
Space Complexity: O(D) for storing the frequency bucket.

Solution

We start by computing the absolute difference for each pair (nums1[i], nums2[i]) and count them in a frequency bucket indexed by the difference value. We then combine the available operations (k = k1 + k2) and simulate reducing the differences from the highest value downward. For a given difference d with a count freq[d]:

  • If the number of available operations is at least the count, we reduce all occurrences by one (i.e. move them to bucket index d-1) and subtract that count from k.
  • If fewer operations are available than the count, we reduce as many as possible from d to d-1 and stop. After processing all the operations (or if all differences become 0), we compute the final sum of squared differences as Σ (d² * freq[d]).
    This bucket simulation ensures we are always reducing the highest differences first, thereby minimizing the total squared sum.

Code Solutions

# Python solution with detailed comments

class Solution:
    def minimumDifference(self, nums1, nums2, k1, k2):
        # Combine the allowed operations from both arrays
        k = k1 + k2
        
        # Compute the absolute differences array
        n = len(nums1)
        diffs = [abs(nums1[i] - nums2[i]) for i in range(n)]
        
        # Find the maximum difference to determine bucket size
        max_diff = max(diffs) if diffs else 0
        
        # Create a frequency bucket for differences from 0 to max_diff
        freq = [0] * (max_diff + 1)
        for diff in diffs:
            freq[diff] += 1
        
        # Process the frequency bucket starting from the largest difference
        for d in range(max_diff, 0, -1):
            if freq[d] == 0:
                continue  # Skip if no element has this difference
            # If available operations can reduce all differences of current value 'd'
            if k >= freq[d]:
                # Reduce all these differences by 1
                freq[d - 1] += freq[d]
                k -= freq[d]
                freq[d] = 0
            else:
                # Only part of the differences can be reduced.
                # Reduce 'k' elements from difference d to d-1.
                freq[d] -= k
                freq[d - 1] += k
                k = 0
                break  # No more operations remain
        
        # Calculate the final sum of squared differences
        result = sum(d * d * count for d, count in enumerate(freq))
        return result

# Example usage:
# sol = Solution()
# print(sol.minimumDifference([1,4,10,12], [5,8,6,9], 1, 1))
← Back to All Questions