Minimum Sum of Absolute Differences

Easy
0/40
Average time to solve is 10m
profile
Contributed by
3 upvotes
Asked in companies
AdobeOlaPharmEasy

Problem statement

You have been given two arrays/lists 'ARR1' and 'ARR2' of length 'N'. Your task is to pair each element of 'ARR1' to an element of 'ARR2' such that the sum of the absolute difference of all pairs is minimum.

Example: 
If 'ARR1' = [0, 2, 1], and 'ARR2' = [8, 10, 4] then the most optimal pairing will be (0, 4) , (1, 8) and (2, 10). The sum of absolute difference will be 4 + 7 + 8 = 19.
Note: 
An element from one array can make a pair only with at most one element of another array.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains a positive integer ‘N’ which represents the length of the array/list.

The second line of each test case contains ‘N’ single space-separated integers representing the elements of the first array/list(ARR1).

The third line of each test case contains ‘N’ single space-separated integers representing the elements of the first array/list(ARR2).
Output Format: 
For each test case, the only line of output will print an integer denoting the minimum sum of absolute difference of all pairs.

Print the output of each test case in a separate line.
Note: 
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 100
1 <= N <= 5000
0 <= ARR1[i] <= 10^5
0 <= ARR2[i] <= 10^5

Time limit: 1 sec
Sample Input 1:
1
5
10 24 5 90 4 
14 2 32 5 6
Sample output 1:
74
Explanation of Sample output 1:
The best way to pair the elements is (4, 2), (5, 5), (10,6), (24, 14), (90, 32). The sum of the absolute difference between pairs is  2 + 0 + 4 + 10 + 58 = 74
Sample Input 2:
2
4 
1 2 3 1
4 5 5 4
5
1 1 1 1 1
1 1 1 1 1
Sample output 2:
11
0
Hint

Try to pair the minimum of both arrays, then the second minimum and so on.

Approaches (2)
NAIVE APPROACH

The best way to pair the elements of the different arrays is to pair the minimum of both arrays, then the second minimum of both arrays, and so on.

 

We will use two ‘paired’ arrays that represent that the ‘i-th’ element has already paired up or not.

Time Complexity

O(N ^ 2), where ‘N’ is the length of the array/list. 

 

We are finding the minimum of both arrays N times and the time complexity for finding the minimum of an array is linear. So, the total time complexity is O(N ^ 2).

Space Complexity

O(N), where ‘N’ is the length of the array/list. 

 

We are using two ‘paired’ arrays of size ‘N’. Hence, the space complexity is linear.

Code Solution
(100% EXP penalty)
Minimum Sum of Absolute Differences
Full screen
Console