Problem Description

You are given two arrays nums1 and nums2 of equal length n, containing positive integers.

The product sum of two equal-length arrays is calculated by multiplying corresponding elements at each position and then adding all these products together. Specifically, for arrays a and b, the product sum equals a[0] * b[0] + a[1] * b[1] + ... + a[n-1] * b[n-1].

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.

Your task is to find the minimum possible product sum by rearranging the elements in nums1 (you can change the order of elements in nums1 however you like, but nums2 remains fixed).

The key insight is that to minimize the product sum, you should pair the largest values in one array with the smallest values in the other array. This is achieved by sorting nums1 in ascending order and nums2 in descending order, then calculating the product sum of these rearranged arrays. This greedy approach ensures that large numbers are multiplied by small numbers, minimizing the overall sum.

Intuition

To minimize the product sum, we need to think about how multiplication works. When we multiply two numbers, the result grows larger when both numbers are large, and stays smaller when at least one of them is small.

Consider a simple example: if we have nums1 = [1, 4] and nums2 = [2, 3]. We can rearrange nums1 to get two possible product sums:

• If nums1 = [1, 4]: product sum = 1*2 + 4*3 = 2 + 12 = 14
• If nums1 = [4, 1]: product sum = 4*2 + 1*3 = 8 + 3 = 11

Notice that the second arrangement gives us a smaller sum. Why? Because we paired the largest number in nums1 (which is 4) with the smallest number in nums2 (which is 2), and the smallest in nums1 (which is 1) with the largest in nums2 (which is 3).

This reveals the key pattern: to minimize the sum of products, we should pair large numbers with small numbers. Think of it as "balancing" - we want to avoid situations where two large numbers multiply together (which would create a very large product).

The greedy strategy emerges naturally: sort one array in ascending order and the other in descending order. This ensures that:

• The largest element in one array gets multiplied by the smallest element in the other
• The second-largest gets multiplied by the second-smallest
• And so on...

This pairing strategy minimizes each individual product term, which in turn minimizes the total sum. Since we can only rearrange nums1, we sort it in ascending order and sort nums2 in descending order (or vice versa - the result would be the same).

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a straightforward greedy approach with sorting:

1. Sort nums1 in ascending order: We use nums1.sort() to arrange the elements from smallest to largest. This ensures that the smallest elements of nums1 will be at the beginning of the array.

2. Sort nums2 in descending order: We use nums2.sort(reverse=True) to arrange the elements from largest to smallest. This ensures that the largest elements of nums2 will be at the beginning of the array.

3. Calculate the product sum: After sorting, we pair up the elements at corresponding positions. The smallest element in nums1 gets multiplied with the largest element in nums2, the second-smallest in nums1 with the second-largest in nums2, and so on.

The calculation is done efficiently using Python's zip() function combined with a generator expression:

• zip(nums1, nums2) creates pairs of elements at the same index from both arrays
• x * y for x, y in zip(nums1, nums2) generates the product of each pair
• sum() adds up all these products to get the final result

For example, if after sorting we have:

• nums1 = [1, 2, 3, 4] (ascending)
• nums2 = [5, 3, 2, 1] (descending)

The product sum would be: 1*5 + 2*3 + 3*2 + 4*1 = 5 + 6 + 6 + 4 = 21

The time complexity is O(n log n) due to the sorting operations, where n is the length of the arrays. The space complexity is O(1) if we consider the sorting to be in-place (though technically Python's sort uses O(n) space).

Example Walkthrough

Let's walk through a concrete example to see how the solution works.

Given:

• nums1 = [3, 5, 1]
• nums2 = [4, 6, 2]

Goal: Find the minimum product sum by rearranging nums1.

Step 1: Sort nums1 in ascending order

nums1.sort() → nums1 = [1, 3, 5]

We arrange nums1 from smallest to largest.

Step 2: Sort nums2 in descending order

nums2.sort(reverse=True) → nums2 = [6, 4, 2]

We arrange nums2 from largest to smallest.

Step 3: Calculate the product sum Now we pair up elements at corresponding positions:

• Position 0: 1 × 6 = 6 (smallest in nums1 × largest in nums2)
• Position 1: 3 × 4 = 12 (middle in nums1 × middle in nums2)
• Position 2: 5 × 2 = 10 (largest in nums1 × smallest in nums2)

Product sum = 6 + 12 + 10 = 28

Why is this minimal? Let's verify by checking another arrangement. If we had kept nums1 as [3, 5, 1]:

• 3 × 4 = 12
• 5 × 6 = 30
• 1 × 2 = 2
• Sum = 12 + 30 + 2 = 44

Notice that 44 > 28. The greedy approach of pairing large with small values prevents situations like 5 × 6 = 30 where two large numbers multiply to create an even larger product. By systematically pairing opposites (largest with smallest), we minimize each individual product term, resulting in the minimum possible sum.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n), where n is the length of the arrays nums1 and nums2.

The time complexity is dominated by the sorting operations:

• nums1.sort() takes O(n × log n) time
• nums2.sort(reverse=True) takes O(n × log n) time
• The zip and sum operations with generator expression take O(n) time

Overall: O(n × log n) + O(n × log n) + O(n) = O(n × log n)

Space Complexity: O(log n), where n is the length of the arrays.

The space complexity comes from:

• Python's Timsort algorithm (used in .sort()) requires O(log n) space for the recursion stack in the worst case
• Both sorting operations are done in-place, so no additional O(n) space is needed for the arrays themselves
• The generator expression (x * y for x, y in zip(nums1, nums2)) uses O(1) space as it generates values on-the-fly

Overall: O(log n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying Input Arrays Without Consideration

The solution sorts both nums1 and nums2 in-place, which permanently modifies the original arrays. This can be problematic if:

• The original array order needs to be preserved for other operations
• The function is called multiple times with the same array references
• The caller expects the arrays to remain unchanged

Example of the issue:

nums1 = [3, 5, 2, 1]
nums2 = [4, 2, 1, 3]
result = minProductSum(nums1, nums2)
# After the function call:
# nums1 is now [1, 2, 3, 5] - permanently changed!
# nums2 is now [4, 3, 2, 1] - permanently changed!

Solution: Create copies of the arrays before sorting:

def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:
    # Create copies to avoid modifying original arrays
    sorted_nums1 = sorted(nums1)  # Creates a new sorted list
    sorted_nums2 = sorted(nums2, reverse=True)  # Creates a new sorted list
  
    min_product_sum = sum(x * y for x, y in zip(sorted_nums1, sorted_nums2))
    return min_product_sum

2. Integer Overflow in Other Languages

While Python handles arbitrarily large integers automatically, implementing this solution in languages like C++ or Java requires careful consideration of integer overflow when dealing with large numbers.

Example scenario:

• If nums1[i] and nums2[i] are both near 10^5 and array length is 10^5
• Each product could be up to 10^10
• The sum could exceed the range of a 32-bit integer

Solution for other languages: Use appropriate data types:

// C++ example
long long minProductSum(vector<int>& nums1, vector<int>& nums2) {
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end(), greater<int>());
  
    long long result = 0;  // Use long long instead of int
    for (int i = 0; i < nums1.size(); i++) {
        result += (long long)nums1[i] * nums2[i];
    }
    return result;
}

3. Assuming Both Arrays Can Be Rearranged

The problem specifically states that only nums1 can be rearranged while nums2 remains fixed. A common mistake is sorting both arrays thinking both can be rearranged freely.

Incorrect interpretation:

# WRONG: This assumes both arrays can be rearranged
nums1.sort()
nums2.sort()  # Should not sort nums2 in ascending order
min_sum = sum(x * y for x, y in zip(nums1, nums2))

Correct approach when only nums1 can be rearranged:

def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:
    # Only sort nums1 based on nums2's values
    # Pair largest in nums2 with smallest in nums1
    nums2_indexed = [(val, idx) for idx, val in enumerate(nums2)]
    nums2_indexed.sort(reverse=True)  # Sort by value descending
  
    nums1.sort()  # Sort nums1 ascending
  
    result = 0
    for i, (val2, original_idx) in enumerate(nums2_indexed):
        result += nums1[i] * val2
  
    return result