Problem

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 _theminimum product sum if you are allowed to rearrange the order of the elements in _nums1.

Examples

Example 1:

1
2
3

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:

1
2
3

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

Solution

Method 1 – Greedy Sorting

Intuition

To minimize the product sum, pair the smallest elements of one array with the largest elements of the other. This way, large values are multiplied by small values, reducing the total sum.

Approach

  1. Sort nums1 in ascending order.
  2. Sort nums2 in descending order.
  3. Multiply corresponding elements and sum the products.
  4. Return the total sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    int minProductSum(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.rbegin(), nums2.rend());
        int ans = 0;
        for (int i = 0; i < nums1.size(); ++i) ans += nums1[i] * nums2[i];
        return ans;
    }
};
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)))
    ans := 0
    for i := range nums1 {
        ans += nums1[i] * nums2[i]
    }
    return ans
}
1
2
3
4
5
6
7
8
9

class Solution {
    public int minProductSum(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int ans = 0, n = nums1.length;
        for (int i = 0; i < n; ++i) ans += nums1[i] * nums2[n-1-i];
        return ans;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun minProductSum(nums1: IntArray, nums2: IntArray): Int {
        nums1.sort()
        nums2.sortDescending()
        var ans = 0
        for (i in nums1.indices) ans += nums1[i] * nums2[i]
        return ans
    }
}
1
2
3
4
5
6
7

def min_product_sum(nums1: list[int], nums2: list[int]) -> int:
    nums1.sort()
    nums2.sort(reverse=True)
    ans = 0
    for a, b in zip(nums1, nums2):
        ans += a * b
    return ans
1
2
3
4
5
6
7
8
9

impl Solution {
    pub fn min_product_sum(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let mut a = nums1.clone();
        let mut b = nums2.clone();
        a.sort();
        b.sort_by(|x, y| y.cmp(x));
        a.iter().zip(b.iter()).map(|(x, y)| x * y).sum()
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    minProductSum(nums1: number[], nums2: number[]): number {
        nums1.sort((a, b) => a - b);
        nums2.sort((a, b) => b - a);
        let ans = 0;
        for (let i = 0; i < nums1.length; ++i) ans += nums1[i] * nums2[i];
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n)
    • Sorting both arrays takes O(n log n) time.
  • 🧺 Space complexity: O(1)
    • Sorting in-place and only a few variables used.