Minimize Product Sum of Two Arrays - Solution & Explanation

Problem Overview: You receive two arrays of equal length. You can reorder the elements of one array. The goal is to minimize the total sum(nums1[i] * nums2[i]). The optimal strategy depends on how you pair large and small values.

Approach 1: Brute Force Permutations (O(n! * n) time, O(n) space)

Generate every permutation of one array and compute the product sum with the other array. Track the minimum across all permutations. Each permutation requires O(n) work to compute the sum, and there are n! permutations. This approach proves the concept but becomes infeasible even for moderate n. Interviewers rarely expect this implementation, but recognizing that order affects the result is the first step toward the greedy insight.

Approach 2: Greedy + Sorting (O(n log n) time, O(1) or O(n) space)

The product sum becomes smaller when large numbers are multiplied by small numbers. Sort nums1 in ascending order and nums2 in descending order. Then iterate once and accumulate nums1[i] * nums2[i]. This pairing forces the smallest value in one array to multiply with the largest value in the other, minimizing each contribution to the total sum. Sorting dominates the runtime, giving O(n log n) time with constant extra space if sorting in place. This is the most common solution using greedy strategy combined with sorting.

Approach 3: Greedy with Counting Sort Optimization (O(n + k) time, O(k) space)

The constraints guarantee that values fall within a small range (for example 1–100 in the original problem). Instead of sorting directly, count the frequency of each value using two frequency arrays. Walk the smallest values of nums1 against the largest values of nums2, multiplying as many pairs as their frequencies allow. This simulates the sorted order without performing an explicit sort. The runtime becomes O(n + k), where k is the value range, which is effectively linear. This approach relies heavily on array frequency counting and works well when ranges are small.

Recommended for interviews: The expected solution is the Greedy + Sorting approach. It demonstrates recognition of the pairing strategy that minimizes sums of products. Mentioning the brute force approach shows you understand the search space, but implementing the greedy pairing with sorted arrays signals strong algorithmic reasoning using array manipulation and ordering techniques.