Minimum Sum of Absolute Differences of Pairs

Problem Statement

You are given two arrays A and B of equal length N. Your task is to pair each element of array A to an element in array B, such that the sum of the absolute differences of all the pairs is minimum.

link to the problem statement could be found here, https://practice.geeksforgeeks.org/problems/minimum-sum-of-absolute-differences-of-pairs/1

Sample Input and Output

Example 1

Input:
N = 4
A = {4,1,8,7}
B = {2,3,6,5}
Output:
6
Explanation:

If we take the pairings as (1,2), (4,3),(7,5), and (8,6), 
the sum will be 
S = |1 - 2| + |4 - 3| + |7 - 5| + |8 - 6|
  = 6
It can be shown that this is the minimum sum we can get.

Expected Time Complexity: O(N*log(N))

Expected Auxiliary Space: O(1)

Solution

Now how to solve this, if you closely look into the problem statement it clearly means the absolute difference should be as minimum as possible.
Let's apply the induction method, now consider 2 arrays

X = [a, d, b, c]
Y = [c, d, b, a]

The minimum comes when for an element a in array X there must be the closest number in Y. So to 'b' within array X should map into array Y. When done this array would look like

X = [a, b, c, d]
Y = [a, b, c, d]
Difference = 0

The bottom line here, is you need to have the same order in both arrays. Which directly means, we need to sort the Array either in ascending or descending order.

Here, I've choosen default natural sorting order, ie, Ascending. By this approach we come up with below solution.

class Solution { 
    long findMinSum(int[] a,int[] b, int n) { 
        if(a.length != b.length) 
            throw new IllegalArgumentException();
        long res = 0l;
        Arrays.sort(a);
        Arrays.sort(b);
        for(int i = 0; i < a.length; i++) {
            res += Math.abs(a[i] - b[i]);
        }
        return res;
    }
}