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 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

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Thank you for reading ^^^^^^^^^^^^^^^

NEW! Following my Trail (Upvote or/and Downvote)

Follow me for topics of Algorithms, Blockchain and Cloud.
I am @justyy - a Steem Witness
https://steemyy.com

My contributions

• Video Downloader
• Steem Blockchain Tools
• Free Cryptos API
• VPS Database
• Computing Technology Blog
• A few useless tools
• And some other online software/tools
• Merge Files/Videos
• LOGO Turtle Programming Chrome Extension
• Teaching Kids Programming - Youtube Channel and All Contents

Delegation Service

1. Voting Algorithm Updated to Favor those High Delegations!

• Delegate 1000 to justyy: Link
• Delegate 5000 to justyy: Link
• Delegate 10000 to justyy: Link

Support me

If you like my work, please:

• Buy Me a Coffee, Thanks!
• Become my Sponsor, Thanks!
• Voting for me:
  https://steemit.com/~witnesses type in justyy and click VOTE
  

1. Delegate SP: https://steemyy.com/sp-delegate-form/?delegatee=justyy
2. Vote @justyy as Witness: https://steemyy.com/witness-voting/?witness=justyy&action=approve
3. Set @justyy as Proxy: https://steemyy.com/witness-voting/?witness=justyy&action=proxy
   Alternatively, you can vote witness or set proxy here: https://steemit.com/~witnesses

---