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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimize Product Sum of Two Arrays

Number: 2029

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given two arrays nums1 and nums2 of equal length, the product sum is defined as the sum of nums1[i] * nums2[i]. You are allowed to rearrange the elements of nums1 to achieve the minimum possible product sum. The task is to determine this smallest product sum.

Key Insights

  • Rearranging nums1 is the only allowed operation.
  • To minimize the product sum, pair the smallest numbers from nums1 with the largest numbers from nums2.
  • Sorting nums1 in ascending order and nums2 in descending order results in the optimal pairing.
  • This greedy approach ensures that large values in nums2 are paired with smaller values in nums1, reducing the overall sum.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) if sorting is done in-place, otherwise O(n).

Solution

Sort nums1 in ascending order and nums2 in descending order. Then, multiply corresponding elements from the two arrays and accumulate the products. This is effective because multiplying the smallest available number from nums1 with the largest available number from nums2 minimizes the contribution to the sum, thereby yielding the minimum product sum.

Code Solutions

def min_product_sum(nums1, nums2):
    # Sort nums1 in ascending order
    nums1.sort()
    # Sort nums2 in descending order
    nums2.sort(reverse=True)
    
    product_sum = 0
    # Multiply corresponding elements from both arrays to get the minimum product sum
    for a, b in zip(nums1, nums2):
        product_sum += a * b
        
    return product_sum

# Example usage:
nums1 = [2, 1, 4, 5, 7]
nums2 = [3, 2, 4, 8, 6]
print(min_product_sum(nums1, nums2))  # Expected Output: 65
← Back to All Questions