Minimum Sum of Absolute Differences of Pairs

Minimum Sum of Absolute Differences of Pairs is a clean greedy problem. You are handed two equal-length arrays and asked to pair every element of one with an element of the other. The twist is choosing the pairing that makes the grand total as small as possible.

The slow way first

There are n! ways to pair the two arrays. Trying them all and keeping the smallest total is correct but factorial — hopeless past a handful of elements. Even being clever with permutations, brute force explodes fast.

The question to ask: is there an arrangement I can argue is always best, without searching? If so, I skip the search entirely.

The idea: sort both, then pair in order

Sort both arrays ascending and pair them position-for-position: smallest with smallest, next with next, largest with largest. This is the greedy choice, and it is provably optimal.

Why does sorting win? If two pairs are ever crossed — a smaller value matched to a larger partner while a larger value takes the smaller partner — uncrossing them (matching small with small) never increases the total and often shrinks it. So the fully sorted, uncrossed arrangement is at the minimum.

Walk through it

Step through the animation. Both rows start unsorted, then snap into ascending order. The pointer sweeps column by column: each column shows |a[i] - b[i]|, and the running total accumulates underneath. By the last column the total is the answer — no search, just one pass after the sort.

Pseudocode

sort a ascending
sort b ascending
total = 0
for each position i:
    total = total + absolute_value(a[i] - b[i])
return total

The Python solution

def min_sum_abs_diff(a, b):
    a.sort()
    b.sort()
    total = 0
    for x, y in zip(a, b):
        total += abs(x - y)
    return total

• a.sort() and b.sort() put both arrays in ascending order — the heart of the greedy choice.
• total accumulates the cost as we go.
• zip(a, b) walks both sorted rows together, handing us one aligned pair (x, y) at a time.
• total += abs(x - y) adds the absolute difference of the current column.
• We return total once every column is paired.

Complexity

Sorting costs O(n log n); the pairing sweep is a single O(n) pass. We need no extra structures beyond the sort, so the auxiliary space is O(1) (ignoring the sort's own bookkeeping).

When this pattern shows up

Practice