LeetCode 1874 - Minimize Product Sum of Two Arrays

LeetCode Problem 1874

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem defines the product sum of two arrays as the sum of the products of corresponding elements at the same indices. If we have arrays a and b, then the product sum is:

$$\sum_{i=0}^{n-1} a[i] \times b[i]$$

We are given two arrays, nums1 and nums2, both of the same length n. We are allowed to rearrange only nums1, while nums2 must remain fixed. Our goal is to reorder nums1 so that the final product sum becomes as small as possible.

The key challenge is deciding which elements in nums1 should be paired with which elements in nums2. Since every element contributes multiplicatively, poor pairings can greatly increase the total sum.

The constraints provide important information about the problem size:

• 1 <= n <= 10^5
• 1 <= nums1[i], nums2[i] <= 100

The array length can be very large, so any factorial or quadratic solution is infeasible. However, the values themselves are very small, only from 1 to 100, which hints that counting techniques may also be possible.

An important observation is that larger numbers should generally be paired with smaller numbers to minimize the total contribution. Pairing large with large produces unnecessarily large products.

Several edge cases are worth considering upfront:

• Arrays of length 1, where no rearrangement matters.
• Arrays where all elements are equal, where every permutation gives the same answer.
• Arrays already arranged optimally or pessimally.
• Large arrays with repeated values.
• Cases where one array contains very large values while the other contains very small values.

The problem guarantees both arrays are non-empty and have equal length, so we do not need to handle invalid inputs.

Approaches

Brute Force Approach

The brute-force idea is to generate every possible permutation of nums1, compute the product sum for each permutation, and return the minimum result.

This works because trying all permutations guarantees that we eventually examine the optimal arrangement.

For each permutation:

1. Rearrange nums1
2. Compute the product sum
3. Track the minimum result seen so far

The problem is that the number of permutations grows factorially. For an array of length n, there are n! possible arrangements.

Even for relatively small values like n = 10, this becomes impractical:

$$10! = 3,628,800$$

The actual constraint allows n up to 100000, making brute force completely impossible.

Optimal Greedy Approach

The key insight comes from understanding how multiplication affects the total sum.

Suppose we have two large numbers paired together:

$$10 \times 9 = 90$$

If instead we pair the large number with a smaller one:

$$10 \times 1 = 10$$

The total contribution becomes much smaller.

To minimize the overall sum, we should:

• Pair the smallest values in nums1 with the largest values in nums2
• Pair the largest values in nums1 with the smallest values in nums2

This is a classic greedy strategy based on the rearrangement inequality.

The implementation is straightforward:

1. Sort nums1 in ascending order
2. Sort nums2 in descending order
3. Multiply corresponding elements
4. Sum the results

This guarantees the minimum possible product sum.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! × n)	O(n)	Tries every permutation of nums1
Optimal Greedy	O(n log n)	O(1) or O(n)	Sort ascending and descending to minimize pair products

Algorithm Walkthrough

Optimal Greedy Algorithm

1. Sort nums1 in ascending order.

We place the smallest values first because we want them paired with the largest values from nums2. 2. Sort nums2 in descending order.

This ensures the largest values appear first and align with the smallest values in nums1. 3. Initialize a variable product_sum to 0.

This variable accumulates the total minimized product sum. 4. Iterate through both arrays simultaneously.

For each index i, compute:

$$nums1[i] \times nums2[i]$$

Add this value to product_sum. 5. Return product_sum.

After processing every pair, the accumulated value is the minimum possible product sum.

Why it works

The correctness comes from the rearrangement inequality. When one sequence is sorted ascending and the other descending, large values are always paired with small values. This minimizes the contribution of each multiplication and therefore minimizes the total sum.

If two large numbers were paired together instead, their product would increase the total unnecessarily. The greedy pairing avoids that situation globally, not just locally.

Python Solution

from typing import List

class Solution:
    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:
        nums1.sort()
        nums2.sort(reverse=True)

        product_sum = 0

        for i in range(len(nums1)):
            product_sum += nums1[i] * nums2[i]

        return product_sum

The implementation begins by sorting nums1 in ascending order and nums2 in descending order. This directly applies the greedy strategy discussed earlier.

The variable product_sum stores the running total. We then iterate through both arrays using their indices. At each step, we multiply the corresponding elements and add the result to the total.

Finally, we return the accumulated sum.

The code is concise because Python's built-in sorting utilities handle the ordering efficiently.

Go Solution

package main

import "sort"

func minProductSum(nums1 []int, nums2 []int) int {
	sort.Ints(nums1)

	sort.Slice(nums2, func(i, j int) bool {
		return nums2[i] > nums2[j]
	})

	productSum := 0

	for i := 0; i < len(nums1); i++ {
		productSum += nums1[i] * nums2[i]
	}

	return productSum
}

The Go implementation follows the same algorithmic structure as the Python version.

sort.Ints is used to sort nums1 in ascending order. For descending order, Go requires a custom comparator through sort.Slice.

The rest of the implementation uses a standard loop to compute the total product sum.

Go slices naturally handle dynamic array behavior, so there is no special handling required for empty arrays because the problem guarantees valid input sizes.

Integer overflow is not an issue under the given constraints. The maximum possible sum is:

$$100 \times 100 \times 100000 = 10^9$$

which safely fits inside Go's int type on standard 64-bit systems.

Worked Examples

Example 1

Input:

nums1 = [5,3,4,2]
nums2 = [4,2,2,5]

Step 1: Sort Arrays

Array	Result
nums1 ascending	[2,3,4,5]
nums2 descending	[5,4,2,2]

Step 2: Compute Product Sum

Index	nums1[i]	nums2[i]	Product	Running Sum
0	2	5	10	10
1	3	4	12	22
2	4	2	8	30
3	5	2	10	40

Final answer:

40

Example 2

Input:

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

Step 1: Sort Arrays

Array	Result
nums1 ascending	[1,2,4,5,7]
nums2 descending	[8,6,4,3,2]

Step 2: Compute Product Sum

Index	nums1[i]	nums2[i]	Product	Running Sum
0	1	8	8	8
1	2	6	12	20
2	4	4	16	36
3	5	3	15	51
4	7	2	14	65

Final answer:

65

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(n)	Depends on the sorting implementation

The algorithm performs two sorting operations, each requiring O(n log n) time. The final traversal to compute the sum is linear.

The auxiliary space depends on the language's sorting implementation. Python's Timsort may use additional memory internally, while Go's sorting implementation also uses stack space during recursion. Conceptually, the algorithm itself only stores a few variables beyond the input arrays.

Test Cases

from typing import List

class Solution:
    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:
        nums1.sort()
        nums2.sort(reverse=True)

        product_sum = 0

        for i in range(len(nums1)):
            product_sum += nums1[i] * nums2[i]

        return product_sum

sol = Solution()

assert sol.minProductSum([5,3,4,2], [4,2,2,5]) == 40  # Example 1
assert sol.minProductSum([2,1,4,5,7], [3,2,4,8,6]) == 65  # Example 2

assert sol.minProductSum([1], [100]) == 100  # Single element arrays

assert sol.minProductSum([1,1,1], [1,1,1]) == 3  # All elements identical

assert sol.minProductSum([1,2,3], [1,2,3]) == 10  # Requires optimal rearrangement

assert sol.minProductSum([100,100,100], [100,100,100]) == 30000  # Maximum values

assert sol.minProductSum([1,100], [100,1]) == 200  # Symmetric large-small pairing

assert sol.minProductSum([9,8,7], [1,2,3]) == 46  # Already optimally arranged

assert sol.minProductSum([1,2,3,4,5], [5,4,3,2,1]) == 35  # Reverse ordered arrays

assert sol.minProductSum([5,5,5,1], [10,1,1,1]) == 20  # Repeated values

Test Case Summary

Test	Why
[5,3,4,2], [4,2,2,5]	Validates example 1
[2,1,4,5,7], [3,2,4,8,6]	Validates example 2
[1], [100]	Smallest valid input size
All identical elements	Confirms permutations do not matter
[1,2,3], [1,2,3]	Ensures greedy rearrangement is applied
All maximum values	Stress test for large products
[1,100], [100,1]	Tests large-small pairing logic
Already optimal ordering	Confirms algorithm preserves optimality
Reverse ordered arrays	Tests sorting correctness
Repeated values	Ensures duplicates are handled correctly

Edge Cases

One important edge case is when the arrays contain only one element. In this scenario, no rearrangement is possible because there is only a single pairing. A careless implementation might still attempt unnecessary sorting or indexing logic, but the provided solution handles this naturally because sorting a single-element array is valid and the loop executes exactly once.

Another important case occurs when all values are identical. For example:

nums1 = [5,5,5]
nums2 = [5,5,5]

Every possible permutation produces the same result. Some algorithms incorrectly assume that rearrangement always changes the outcome, but the greedy method still works correctly because sorting preserves the values and the final sum remains unchanged.

A third important edge case involves highly unbalanced values, such as:

nums1 = [1,100]
nums2 = [1,100]

A naive implementation that pairs elements in their original order produces:

$$1 \times 1 + 100 \times 100 = 10001$$

The optimal arrangement instead produces:

$$1 \times 100 + 100 \times 1 = 200$$

This demonstrates why sorting in opposite directions is essential. The implementation explicitly guarantees this pairing strategy by sorting one array ascending and the other descending.

Another subtle edge case is large input size with many duplicates. Since n can reach 100000, inefficient approaches become infeasible. The sorting-based solution remains efficient enough for the constraints and handles repeated values naturally without any additional logic.