Algorithm to Minimize Product Sum of Two Arrays


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 1*5 + 2*2 + 3*3 + 4*1 = 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 3*4 + 5*2 + 4*2 + 2*5 = 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 5*3 + 7*2 + 4*4 + 1*8 + 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.

1
2
3
4
5
6
7
8
9
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
}
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.

1
2
3
4
5
6
7
8
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
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:

1
2
3
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]))])
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.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
431 words
Last Post: Backtracking Algorithm to Solve N Queens Puzzle (Partially Filled)
Next Post: Teaching Kids Programming - Rotate a 2D Matrix/Image 90 Degree Clockwise

The Permanent URL is: Algorithm to Minimize Product Sum of Two Arrays

Leave a Reply