Minimize Product Sum of Two Arrays solution and explanation
Google
3 more videos on this problem
Minimize Product Sum of Two Arrays | Counting Sort | JavaTea and Code · 11:56 · 935 views
1874. Minimize Product Sum of Two Arrays - Week 2/5 Leetcode December ChallengeProgramming Live with Larry · 3:43 · 276 views
1874. Minimize Product Sum of Two Arrays (Español)Programando ando · 13:51 · 100 views
LeetCode 1874: Minimize Product Sum of Two ArraysAlitaCode · 27:07 · 1 view
The 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]andb = [5,2,3,1], the product sum would be1*5 + 2*2 + 3*3 + 4*1 = 22.
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:
n == nums1.length == nums2.length1 <= n <= 1051 <= nums1[i], nums2[i] <= 100
Approach overview
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.
Solution
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 times log n), and the space complexity is O(log n). Here, n is the length of the array nums1.
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))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;
}
}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;
}
};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;
}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
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutations | O(n! * n) | O(n) | Conceptual understanding or very small arrays |
| Greedy + Sorting | O(n log n) | O(1) or O(n) | General case; most common interview solution |
| Greedy + Counting Sort | O(n + k) | O(k) | When values lie in a small bounded range |
Frequently asked questions
Is Minimize Product Sum of Two Arrays easy or hard?
This problem is rated Medium because the key insight is recognizing the greedy pairing strategy. Once you realize that smallest values should multiply with the largest values, the implementation becomes straightforward using sorting and a single pass.
Minimize Product Sum of Two Arrays Python/Java solution
Most implementations sort one array ascending and the other descending, then compute the sum of pairwise products in a single loop. Python typically uses built-in sort with reverse ordering, while Java uses Arrays.sort and manual reverse indexing. The logic remains identical across languages.
How to solve Minimize Product Sum of Two Arrays in O(n)?
Achieving near-linear time is possible with counting sort if the element values fall within a limited range. Build frequency arrays for both inputs, then match the smallest values of one array with the largest values of the other using the counts. This avoids explicit sorting and runs in O(n + k), where k is the value range.
What is the best approach for Minimize Product Sum of Two Arrays?
The best approach uses a greedy strategy with sorting. Sort the first array in ascending order and the second array in descending order, then multiply corresponding elements and sum them. Pairing the smallest value with the largest minimizes each product contribution. This solution runs in O(n log n) time due to sorting.
Is Minimize Product Sum of Two Arrays asked at Google/Amazon/Meta?
Greedy pairing and array reordering problems appear frequently in interviews at large tech companies including Amazon, Google, and Meta. While the exact problem may vary, the core idea—pairing extremes after sorting to optimize a metric—is a common interview pattern.
What data structure is used in Minimize Product Sum of Two Arrays?
The main data structures are arrays and optionally frequency arrays. The greedy solution relies on sorting arrays, while the optimized version uses counting arrays to simulate sorted order. No complex structures like trees or heaps are required.
What is the time complexity of Minimize Product Sum of Two Arrays?
The standard greedy solution runs in O(n log n) time because both arrays must be sorted before pairing elements. The space complexity is O(1) if sorting happens in place. With a counting sort optimization (when values are bounded), the complexity can be reduced to O(n + k).