Minimize Product Sum of Two Arrays - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

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

MediumPremiumFree on FleetCodeArray Greedy Sorting6 min readAsked at: Google

Practice this problem

Problem Statement

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] and b = [5,2,3,1], the product sum would be 1*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.length
1 <= n <= 10⁵
1 <= 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.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed 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

Video Solution

Minimize Product Sum of Two Arrays | Counting Sort | Java • Tea and Code • 935 views views

Watch 3 more video solutions →

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

Ready to solve this problem?

Practice Minimize Product Sum of Two Arrays with our built-in code editor and test cases.

Practice on FleetCode

Choose Numbers From Two Arrays in Range

Problem Info

DifficultyMedium

Acceptance89.5%

Approaches1

Reading time6 min

Asked at

Google