Minimum Sum of Products of Two Arrays

Minimum Sum of Products of Two Arrays is a clean greedy problem. Given two arrays of equal length, you may reorder each one freely, then you sum the products of matching positions. The goal: make that sum as small as possible.

The slow way first

The brute-force idea: try every possible pairing of a against b. With n elements there are n! permutations of one array against the other — for n = 10 that is already over three million arrangements. Computing the sum for each is hopelessly slow. We need a rule that picks the best pairing directly.

The question to ask: which value should the largest element of one array meet? Intuitively, a large value hurts the total most, so it should be multiplied by the smallest available partner to keep the product down.

The idea: big meets small

Sort a ascending and b descending. Now the smallest element of a lines up with the largest of b, and the largest of a lines up with the smallest of b. Sum the element-wise products. This "rearrangement" pairing always gives the minimum.

This is the rearrangement inequality: a sum of paired products is smallest when one sequence is sorted opposite to the other. We do not have to prove it from scratch in an interview, but knowing the name signals you understand why the greedy choice is correct.

Walk through it

Step through the animation. First both rows snap into sorted order — a increasing, b decreasing. Then we pair column by column: 1×6, 3×4, 5×2, accumulating the running total. After the last pair the total is 28, the minimum possible.

Pseudocode

sort a in ascending order
sort b in descending order
total = 0
for i from 0 to n-1:
    total = total + a[i] * b[i]   # big paired with small
return total

The Python solution

def min_sum_product(a, b):
    a.sort()
    b.sort(reverse=True)
    total = 0
    for x, y in zip(a, b):
        total += x * y
    return total

• a.sort() puts a in ascending order.
• b.sort(reverse=True) puts b in descending order — the opposite direction.
• zip(a, b) walks both sorted arrays in lockstep, handing back matching pairs.
• Each iteration adds one product x * y to total. Because the arrays are sorted oppositely, every large value is multiplied by a small one.
• We return total, which is provably the minimum over all reorderings.

Complexity

The work is two sorts, each O(n log n), followed by a single O(n) pass to sum the products. Sorting in place uses no extra space beyond the arrays themselves.

When this pattern shows up

Practice