1874

1874. Minimize Product Sum of Two Arrays (Medium)

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 <= 105
• 1 <= nums1[i], nums2[i] <= 100

Companies:
Google

Related Topics:
Array, Greedy, Sorting

Similar Questions:

• Choose Numbers From Two Arrays in Range (Hard)

Solution 1. Greedy

// OJ: https://leetcode.com/problems/minimize-product-sum-of-two-arrays/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int minProductSum(vector<int>& A, vector<int>& B) {
        sort(begin(A), end(A));
        sort(begin(B), end(B), greater<>());
        int ans = 0;
        for (int i = 0; i < A.size(); ++i) ans += A[i] * B[i];
        return ans;
    }
};

Solution 2. Counting Sort

// OJ: https://leetcode.com/problems/minimize-product-sum-of-two-arrays/
// Author: github.com/lzl124631x
// Time: O(N + K) where `K` is the range of values in `A` and `B`.
// Space: O(K)
class Solution {
public:
    int minProductSum(vector<int>& A, vector<int>& B) {
        int ca[101] = {}, cb[101] = {}, ans = 0;
        for (int n : A) ca[n]++;
        for (int n : B) cb[n]++;
        for (int i = 1, j = 100, cnt = 0; cnt < A.size();) {
            while (i < 101 && ca[i] == 0) ++i;
            while (j > 0 && cb[j] == 0) --j;
            int d = min(ca[i], cb[j]);
            ans += i * j * d;
            ca[i] -= d;
            cb[j] -= d;
            cnt += d;
        }
        return ans;
    }
};