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

Description Hints 2 Solution Video 11:56

1874. Minimize Product Sum of Two Arrays

Medium89.5% acceptance1 companyPremium elsewhere, free here

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

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

Is there a particular way we should order the arrays such that the product sum is minimized?

Hint 2

Would you want to multiply two numbers that are closer to one another or further?

11:56

Still stuck?Read the written solution, or watch a walkthrough.

Open solution