LeetCode 1874. Minimize Product Sum of Two Arrays Solution in Java, C++, Python & More | Explanation + Code

Description

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

<li>For example, if <code>a = [1,2,3,4]</code> and <code>b = [5,2,3,1]</code>, the <strong>product sum</strong> would be <code>1*5 + 2*2 + 3*3 + 4*1 = 22</code>.</li>

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:

<li><code>n == nums1.length == nums2.length</code></li>

<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>

<li><code>1 &lt;= nums1[i], nums2[i] &lt;= 100</code></li>

Solutions

Solution 1: Greedy + Sorting

Since both arrays consist of positive integers, to minimize the sum of products, we can multiply the largest value in one array with the smallest value in the other array, the second largest with the second smallest, and so on.

Therefore, we sort the array nums1 in ascending order and the array nums2 in descending order. Then, we multiply the corresponding elements of the two arrays and sum the results.

The time complexity is O(n × log n), and the space complexity is O(log n). Here, n is the length of the array nums1.

PythonJavaC++GoTypeScript

class Solution: def minProductSum(self, nums1: List[int], nums2: List[int]) -> int: nums1.sort() nums2.sort(reverse=True) return sum(x * y for x, y in zip(nums1, nums2))(code-box)

class Solution { public int minProductSum(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); int n = nums1.length; int ans = 0; for (int i = 0; i < n; ++i) { ans += nums1[i] * nums2[n - i - 1]; } return ans; } }(code-box)

class Solution { public: int minProductSum(vector<int>& nums1, vector<int>& nums2) { ranges::sort(nums1); ranges::sort(nums2, greater<int>()); int n = nums1.size(); int ans = 0; for (int i = 0; i < n; ++i) { ans += nums1[i] * nums2[i]; } return ans; } };(code-box)

func minProductSum(nums1 []int, nums2 []int) (ans int) { sort.Ints(nums1) sort.Ints(nums2) for i, x := range nums1 { ans += x * nums2[len(nums2)-1-i] } return }(code-box)

function 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; }(code-box)