144. Minimum Sum of Absolute Differences of Pairs of Two Arrays

Given two arrays a and b, each with n integers, pair up every element of a with a distinct element of b (forming n pairs total) so as to minimize the sum of absolute differences across all pairs. Print that minimum sum.

Input: The first line contains an integer n. The second line contains n space-separated integers, array a. The third line contains n space-separated integers, array b. Output: Print a single integer - the minimum possible sum of absolute differences after pairing every element of a with a distinct element of b.

1 <= n <= 10^5

This 'sort both, pair in matching order' technique is a broadly reusable pattern whenever a problem asks to minimize a sum of paired differences between two independent collections.

Pair up elements from two arrays to minimize the sum of absolute differences across all pairs. Brute force: Try every possible pairing (permutation) between the two arrays and compute the sum of absolute differences for each - this is factorial time, impractical for large n. Optimised: Sorting both arrays and pairing them in the SAME relative order is provably optimal - any 'crossing' pairing (where a larger element from one array is paired with a smaller element from the other, out of sorted order) can always be improved by swapping to match sorted order instead, via a straightforward exchange argument.

Repeatedly scan through the remaining unmatched elements of a and b to find the pair with the currently smallest absolute difference, match them together, remove both from further consideration, and repeat until all elements are paired. This greedy nearest-neighbor idea reduces the search space compared to trying every full permutation, but re-scanning both remaining arrays for every single pairing decision still costs a nested loop's worth of work overall. Time: O(n^2) Space: O(n)

Sort array a and array b independently in ascending order, then pair them up index by index (a[i] with b[i] for every i). This minimizes the total sum of absolute differences because any pairing that isn't in this 'same relative rank' order can be shown (via a simple exchange argument: swapping two out-of-order pairs never increases, and can only decrease, the total difference) to be improvable by re-sorting, so the fully sorted pairing is globally optimal. This is a large improvement over both the brute-force and greedy nearest-match approaches since it only requires two sorts and a single linear pass to sum the differences. Time: O(n log n) Space: O(1) extra, beyond the sort

Consider every possible way of matching each element of array a to a distinct element of array b (every permutation of b relative to a), compute the sum of absolute differences for each complete pairing, and keep the smallest sum found. This is guaranteed correct since it examines every possible pairing exhaustively, but the number of permutations grows factorially with n, making it usable only for tiny inputs. Time: O(n!) Space: O(n)

1. Sort both arrays independently in ascending order. 2. Pair them up index-by-index after sorting (smallest with smallest, second-smallest with second-smallest, and so on). 3. Sum the absolute differences of these sorted-position pairs - this is provably the minimum possible.

Time: O(n log n), dominated by sorting both arrays. Space: O(1) extra space beyond sorting the arrays in place (or O(n) if sorting requires extra space).

n = 1 (a single forced pairing), duplicate values within either array, and n at its maximum of 10^5 to confirm the sort-and-pair approach runs efficiently.

Be ready to walk through the exchange-argument proof briefly (why swapping a crossing pair to match sorted order never increases the total) - this is a classic, elegant greedy-correctness proof worth having ready.