Problem Description

You are given two arrays, nums1 and nums2, each containing n positive integers. Your task is to rearrange (permute) the elements of nums1 and nums2 such that the product sum of the arrays is minimized. The product sum is defined as:

productSum = nums1[0] * nums2[0] + nums1[1] * nums2[1] + ... + nums1[n-1] * nums2[n-1]

• You must use each element from both arrays exactly once (no element can be reused or omitted).
• There is always at least one valid solution.
• The arrays may be rearranged in any order before pairing their elements.

Return the minimum possible product sum you can achieve by rearranging the arrays.

Thought Process

The naive or brute-force way to solve this problem would be to try all possible permutations of both arrays, compute the product sum for each, and pick the minimum. However, this approach is not practical, especially for larger arrays, because the number of permutations grows extremely fast (factorial time).

To optimize, we can think about how to pair numbers from the two arrays to minimize the total sum. Intuitively, pairing the largest number from one array with the smallest from the other will minimize the products, since big numbers multiplied by small numbers yield smaller results than big-by-big or small-by-small. This leads us to consider sorting one array in ascending order and the other in descending order before pairing their elements.

This is a classic example of the greedy algorithm approach, where making locally optimal choices (pairing smallest with largest) leads to a globally optimal solution.

Solution Approach

We can solve the problem efficiently using the following steps:

1. Sort nums1 in ascending order: This arranges the smallest values at the front.
2. Sort nums2 in descending order: This arranges the largest values at the front.
3. Pair elements by index: Multiply nums1[i] with nums2[i] for all valid indices.
4. Sum the products: Add up all the products to get the minimum product sum.

Why does this work? By always pairing the smallest available number with the largest, we ensure that the contribution of large numbers to the sum is minimized, and the sum remains as small as possible.

Example Walkthrough

Let's consider the following example:

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

1. Sort nums1 ascending: [1, 2, 3, 5]
2. Sort nums2 descending: [8, 4, 2, 1]
3. Pair and multiply:
   • 1 * 8 = 8
   • 2 * 4 = 8
   • 3 * 2 = 6
   • 5 * 1 = 5
4. Sum the products: 8 + 8 + 6 + 5 = 27

Thus, the minimum product sum for these arrays is 27.

Code Implementation

class Solution:
    def minProductSum(self, nums1, nums2):
        nums1.sort()
        nums2.sort(reverse=True)
        return sum(a * b for a, b in zip(nums1, nums2))
      

class Solution {
   public:
    int minProductSum(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.rbegin(), nums2.rend());
        int sum = 0;
        for (int i = 0; i < nums1.size(); ++i) {
            sum += nums1[i] * nums2[i];
        }
        return sum;
    }
};
      

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

var minProductSum = function(nums1, nums2) {
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => b - a);
    let sum = 0;
    for (let i = 0; i < nums1.length; i++) {
        sum += nums1[i] * nums2[i];
    }
    return sum;
};
      

Time and Space Complexity

Brute-force Approach:

• Time Complexity: O((n!)²) — because there are n! permutations for each array, and for each pair, we compute the sum.
• Space Complexity: O(n) for storing permutations and temporary arrays.

• Time Complexity: O(n log n) — dominated by the sorting of the arrays.
• Space Complexity: O(1) extra (if sorting in-place), or O(n) if you create copies.

The optimized approach is vastly superior, especially for larger input sizes.

Summary

To minimize the product sum of two arrays, the key insight is to pair the smallest numbers from one array with the largest from the other. This greedy strategy is implemented by sorting one array in ascending order and the other in descending order, then summing the products of corresponding pairs. This approach is both elegant and efficient, reducing the problem from factorial to logarithmic complexity, and is easily implemented in any major programming language.