Minimize Absolute Differences - Pair Elements to Minimize Total Absolute Difference

Question

## Problem

Given two arrays `A` and `B` of equal length `n`, pair each element of `A` with exactly one element of `B` (bijection). Minimize the total sum of absolute differences: `sum(|A[i] - B[perm[i]]|)`.

Return the minimum total sum.

```python
def min_abs_diff_sum(A: list[int], B: list[int]) -> int:
```

## Example

```
A = [1, 3, 5], B = [2, 4, 6]
Optimal pairing: (1,2),(3,4),(5,6) -> |1|+|1|+|1| = 3
Output: 3

A = [1, 5], B = [3, 8]
Pairing (1,3),(5,8) -> 2+3=5
Pairing (1,8),(5,3) -> 7+2=9
Output: 5
```

Proof sketch: sorting both arrays and pairing by rank is optimal (exchange argument).

## Follow-ups

1. Prove by exchange argument that sorting both arrays and pairing them in order is always optimal.
2. What if the arrays have different lengths -- how do you choose which elements of the larger array to use?
3. What if instead of absolute difference you want to minimize the maximum difference across all pairs?
4. How does the problem change for 2D points (minimize sum of Euclidean distances)?

Minimize Absolute Differences - Pair Elements to Minimize Total Absolute Difference

Question Details

Full Details

Topics

More from Amazon