Minimum sum of absolute difference of pairs of two arrays

The problem, simply

You get two lists, a and b, with the same number of numbers. Pair every number in a with exactly one number in b. A pair costs the gap between its two numbers, |a[i] - b[j]|.

Give back the smallest possible total cost of all pairs.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep a in place and try every order of b. Each order is one way to pair the lists. Add up the gaps and keep the smallest total.

class Solution {
    private long best;

    public long minPairGap(int[] a, int[] b) {
        best = Long.MAX_VALUE;
        tryOrders(a, b, 0);
        return best;
    }

    private void tryOrders(int[] a, int[] b, int start) {
        if (start == b.length) {
            long total = 0;
            for (int i = 0; i < a.length; i++) total += Math.abs((long) a[i] - b[i]);
            best = Math.min(best, total);
            return;
        }
        for (int i = start; i < b.length; i++) {
            swap(b, start, i);                 // choose who partners a[start]
            tryOrders(a, b, start + 1);
            swap(b, start, i);
        }
    }

    private void swap(int[] x, int i, int j) { int t = x[i]; x[i] = x[j]; x[j] = t; }
}

How long it takes: n! pairings, each added up in n steps, so O(n! * n). Extra room: recursion n deep, O(n).

Way 2: the clever way

Crossed pairs are never better. Say x <= y in a and p <= q in b. Pairing x with q and y with p crosses the pairs. Pairing x with p and y with q keeps them straight, and on a number line you can check that the straight pairs never cost more. So fix every crossing and you end with both lists in sorted order.

1. Sort a.
2. Sort b.
3. Add |a[i] - b[i]| for every i.

import java.util.Arrays;

class Solution {
    public long minPairGap(int[] a, int[] b) {
        Arrays.sort(a);
        Arrays.sort(b);
        long total = 0;
        for (int i = 0; i < a.length; i++) {
            total += Math.abs((long) a[i] - b[i]);   // i-th smallest with i-th smallest
        }
        return total;
    }
}

How long it takes: two sorts, O(n log n), then one walk, O(n). Extra room: O(1) beyond sorting in place.

Watch out for

• Sort both lists the same way, both small to big. Sorting one up and one down gives the largest total, not the smallest.
• The lists must have the same length. If they do not, the problem is different (see below).
• The answer only needs the total. If you must report the pairs, remember each number's original index before sorting.

What interviewers ask next

• The largest total instead? Sort one list up and the other down, so the smallest meets the biggest.
• What if b is longer and each number in a must pick a different partner from b? Now some numbers in b are left out, and greedy is not enough. Use dynamic programming over both sorted lists: dp[i][j] is the best cost using the first i of a and the first j of b.
• What if the cost is a general table, not a gap on a number line? That is the assignment problem, solved by the Hungarian algorithm in O(n^3).
• The pairs are fixed by position (a[i] with b[i]), and you may overwrite one a[i] with a copy of any other number from a. Sort a copy of a and, for each b[i], binary search the closest value to see how much that one change saves. This is LeetCode "Minimum Absolute Sum Difference".

Remember this

Grown-up words: the dance pairs are a matching, the cost is the sum of absolute differences, and uncrossing pairs is an exchange argument.