Minimum sum of absolute difference of pairs of two arrays

Problem Statement

Given two arrays a[] and b[] of equal length n, pair up elements such that each element from a is paired with exactly one element from b, and the sum of absolute differences of all pairs is minimized.

Constraints:

• 1 ≤ n ≤ 10^5
• -10^9 ≤ a[i], b[i] ≤ 10^9

Example:

• Input: a = [4, 1, 8, 7], b = [2, 3, 6, 5]
• Output: 6
• Explanation: Optimal pairing: (1,2), (4,3), (7,6), (8,5) → |1-2| + |4-3| + |7-6| + |8-5| = 1 + 1 + 1 + 3 = 6

Example 2:

• Input: a = [1, 2, 3], b = [3, 2, 1]
• Output: 0
• Explanation: Pair (1,1), (2,2), (3,3) → 0 + 0 + 0 = 0

Approach 1: Brute Force (All Permutations)

Intuition

Try all possible pairings by generating all permutations of one array and pairing with the other. Calculate the sum of absolute differences for each configuration and return the minimum.

Algorithm

1. Fix array a and generate all permutations of array b
2. For each permutation, calculate sum of |a[i] - b[i]| for all i
3. Track and return the minimum sum

import java.util.*;

public class Solution {
    private int minSum = Integer.MAX_VALUE;
    
    private void permute(int[] a, int[] b, int start) {
        if (start == b.length) {
            int sum = 0;
            for (int i = 0; i < a.length; i++) {
                sum += Math.abs(a[i] - b[i]);
            }
            minSum = Math.min(minSum, sum);
            return;
        }
        
        for (int i = start; i < b.length; i++) {
            swap(b, start, i);
            permute(a, b, start + 1);
            swap(b, start, i);
        }
    }
    
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public int minAbsDiffSum(int[] a, int[] b) {
        minSum = Integer.MAX_VALUE;
        permute(a, b, 0);
        return minSum;
    }
}

Complexity Analysis

• Time Complexity: O(n!) - Generating all permutations
• Space Complexity: O(n) - Recursion stack depth

Approach 2: Greedy with Sorting (Optimal)

Intuition

To minimize the sum of absolute differences, we should pair the smallest element of a with the smallest element of b, the second smallest with the second smallest, and so on.

Why does this work? Sorting both arrays ensures that we're pairing elements that are closest in their relative rankings. Any other pairing would result in larger differences because we'd be pairing elements that are farther apart in the sorted order.

Proof by Exchange Argument: If we have pairs (a1, b1) and (a2, b2) where a1 < a2 and b1 > b2, swapping to (a1, b2) and (a2, b1) will never increase the total sum (and often decreases it).

Algorithm

1. Sort both arrays
2. Pair elements at the same index
3. Calculate sum of absolute differences

import java.util.*;

public class Solution {
    public long minAbsDiffSum(int[] a, int[] b) {
        int n = a.length;
        
        Arrays.sort(a);
        Arrays.sort(b);
        
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += Math.abs((long)a[i] - b[i]);
        }
        
        return sum;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] a = {4, 1, 8, 7};
        int[] b = {2, 3, 6, 5};
        System.out.println(sol.minAbsDiffSum(a, b));  // Output: 6
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n log n) - Dominated by sorting both arrays
• Space Complexity: O(1) - Only using constant extra space (or O(n) depending on sort implementation)

Variant: Minimum Sum with Modifications Allowed

Problem

Given arrays a and b, you can modify elements in a by at most k units total. Find minimum sum of absolute differences.

Key Takeaways

1. Greedy Strategy: Sort both arrays and pair elements at same indices
2. Exchange Argument: Proves that sorted pairing is optimal
3. Mathematical Insight: Pairing closest ranked elements minimizes total difference
4. Time Efficiency: O(n log n) due to sorting, O(n) for the actual pairing
5. Space Efficiency: In-place sorting achieves O(1) extra space
6. Similar Problems: Assignment problems, minimum cost matching
7. Extension: Can be extended with modifications using priority queues