Algorithm to Minimize Product Sum of Two Arrays

justyy (82)in #programming • 4 years ago

The product sum of two equal-length arrays a and b is equal to the sum of a[i] * b[i] for all 0 <= i < a.length (0-indexed).
For example, if a = [1,2,3,4] and b = [5,2,3,1], the product sum would be 15 + 22 + 33 + 41 = 22.
Given two arrays nums1 and nums2 of length n, return the minimum product sum if you are allowed to rearrange the order of the elements in nums1.

Example 1:
Input: nums1 = [5,3,4,2], nums2 = [4,2,2,5]
Output: 40
Explanation: We can rearrange nums1 to become [3,5,4,2]. The product sum of [3,5,4,2] and [4,2,2,5] is 34 + 52 + 42 + 25 = 40.

Example 2:
Input: nums1 = [2,1,4,5,7], nums2 = [3,2,4,8,6]
Output: 65
Explanation: We can rearrange nums1 to become [5,7,4,1,2]. The product sum of [5,7,4,1,2] and [3,2,4,8,6] is 53 + 72 + 44 + 18 + 2*6 = 65.

Constraints:
n == nums1.length == nums2.length
1 <= n <= 10^5
1 <= nums1[i], nums2[i] <= 100

We want to minimize the sum of products, and as each number is non-negative, we want to pair the largest with the smallest. Thus, we can sort the arrays one in ascending and another in reversed order, then compute the dot product - which is the sum of the product.

GoLang: Minimize Product Sum of Two Arrays

Sorting in GoLang in reversed is a bit verbose - we need to sort.Reverse as the following.

func minProductSum(nums1 []int, nums2 []int) int {
    sort.Ints(nums1)
    sort.Sort(sort.Reverse(sort.IntSlice(nums2)))
    var ans = 0
    for i := 0; i < len(nums1); i ++ {
        ans += nums1[i] * nums2[i]
    }
    return ans
}

Python: Minimize Product Sum of Two Arrays

Python implementation of computing the min product sum.

class Solution:
    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:
        nums1.sort()
        nums2.sort(reverse=True)
        ans = 0
        for i in range(len(nums1)):
            ans += nums1[i] * nums2[i]
        return ans

Alternatively, we can use the python one liner:

class Solution:
    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:
        return sum([p*q for (p,q) in list(zip(sorted(nums1),sorted(nums2)[::-1]))])

All implementations take O(NLogN) time (where N is the total size length for two arrays) and O(1) space.

Reposted from Blog