Given two arrays a[] and b[] of size N and M respectively (N < M), the task is to find the minimum possible sum of absolute difference of pairs formed by pairing each element of array a[] with an element of array b[]
Note: Each element of each array can be considered only once.
Examples:
Input: a[] = {2, 3, 5}, b[] = {1, 2, 3, 4, 5}
Output: 0
Explanation: Elements {2, 3, 5} in array a[] can be paired with {2, 3, 5} in array b[].
This will give a minimum absolute difference of 0.Input: a[] = {1, 4, 5, 8}, b[] = {1, 3, 4, 6, 7}
Output: 2
Naive approach: The easiest way is to sort the arrays and try all the possible combinations to choose N elements from b[] and make pairs with a[].
Time Complexity: O(N*logN + M*logM + MCN)
Auxiliary Space: O(1)
Efficient Approach: This problem can be efficiently solved by using the concept of dynamic programming using the following idea.
For each element at ith position of array a[], the jth element of b[] can either be used to form a pair with a[i] or not.
So the overlapping subproblem property can be used to form a dp[][] array to store the minimum absolute difference till ith element of b[] and jth element of a[] is considered and can be reused for further calculations.
Follow the steps mentioned below to implement the above idea:
- First sort both arrays.
- Initialize a matrix dp[][] where dp[i][j] indicates the total minimum absolute difference till the index ith index of b[] and jth index of a[].
- While iterating through the index of the larger array b[], at each point of iterations there can be two cases:
- Not taking the ith index into consideration of forming pair with minimum absolute difference sum. Then dp[i+1][j] = dp[i][j] as ith index is not considered and are moving to (i+1)th index directly.
- Considering the ith index. So add the absolute difference between elements at both ith and jth index and then move to (i+1)th and (j+1)th index respectively. So total value is dp[i+1][j+1] = dp[i][j] + abs(a[j] – b[i]).
- The value at dp[M][N] is the required answer.
Below is the implementation of the above approach.
C++
// C++ code to implement above approach#include <bits/stdc++.h>using namespace std;// Function to return the// minimum absolute differenceint min_sum(int a[], int b[], int N, int M){ // Sorting both the arrays sort(a, a + N); sort(b, b + M); int dp[M + 1][N + 1]; // Initialising the dp to high value for (int i = 0; i <= M; i++) { for (int j = 0; j <= N; j++) { dp[i][j] = 1e9; } } dp[0][0] = 0; // Iterating through each element // of the larger array b for (int i = 0; i < M; i++) { // Case 1. Where we are not taking // the element at ith index for (int j = 0; j <= N; j++) { dp[i + 1][j] = dp[i][j]; } // Case 2. When we have to take the // element at ith index for (int j = 0; j < N; j++) { dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(a[j] - b[i])); } } return dp[M][N];}// Driver codeint main(){ int a[] = { 1, 4, 5, 8 }; int N = sizeof(a) / sizeof(a[0]); int b[] = { 1, 3, 4, 6, 7 }; int M = sizeof(b) / sizeof(b[0]); // Function call cout << min_sum(a, b, N, M); return 0;} |
Java
// Java program to implement above approachimport java.util.*;class GFG { // Function to return the // minimum absolute difference static int min_sum(int[] a, int[] b, int N, int M) { // Sorting both the arrays Arrays.sort(a); Arrays.sort(b); int[][] dp = new int[M + 1][N + 1]; // Initialising the dp to high value for (int i = 0; i <= M; i++) { for (int j = 0; j <= N; j++) { dp[i][j] = 1000000000; } } dp[0][0] = 0; // Iterating through each element // of the larger array b for (int i = 0; i < M; i++) { // Case 1. Where we are not taking // the element at ith index for (int j = 0; j <= N; j++) { dp[i + 1][j] = dp[i][j]; } // Case 2. When we have to take the // element at ith index for (int j = 0; j < N; j++) { dp[i + 1][ j + 1] = Math.min(dp[i + 1][j + 1], dp[i][j] + Math.abs(a[j] - b[i])); } } return dp[M][N]; }// Driver Codepublic static void main(String args[]){ int[] a = { 1, 4, 5, 8 }; int N = a.length; int[] b = { 1, 3, 4, 6, 7 }; int M = b.length; // Function call System.out.print(min_sum(a, b, N, M));}}// This code is contributed by code_hunt. |
Python3
# python3 code to implement above approach# Function to return the# minimum absolute differencedef min_sum(a, b, N, M): # Sorting both the arrays a.sort() b.sort() dp = [[0 for _ in range(N+1)] for _ in range(M+1)] # Initialising the dp to high value for i in range(0, M + 1): for j in range(0, N+1): dp[i][j] = int(1e9) dp[0][0] = 0 # Iterating through each element # of the larger array b for i in range(0, M): # Case 1. Where we are not taking # the element at ith index for j in range(0, N+1): dp[i + 1][j] = dp[i][j] # Case 2. When we have to take the # element at ith index for j in range(0, N): dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(a[j] - b[i])) return dp[M][N]# Driver codeif __name__ == "__main__": a = [1, 4, 5, 8] N = len(a) b = [1, 3, 4, 6, 7] M = len(b) # Function call print(min_sum(a, b, N, M)) # This code is contributed by rakeshsahni |
C#
// C# code to implement above approachusing System;public class GFG{ // Function to return the // minimum absolute difference static int min_sum(int[] a, int[] b, int N, int M) { // Sorting both the arrays Array.Sort(a); Array.Sort(b); int[,] dp = new int[M + 1, N + 1]; // Initialising the dp to high value for (int i = 0; i <= M; i++) { for (int j = 0; j <= N; j++) { dp[i,j] = 1000000000; } } dp[0,0] = 0; // Iterating through each element // of the larger array b for (int i = 0; i < M; i++) { // Case 1. Where we are not taking // the element at ith index for (int j = 0; j <= N; j++) { dp[i + 1, j] = dp[i, j]; } // Case 2. When we have to take the // element at ith index for (int j = 0; j < N; j++) { dp[i + 1, j + 1] = Math.Min(dp[i + 1, j + 1], dp[i, j] + Math.Abs(a[j] - b[i])); } } return dp[M, N]; } // Driver code static public void Main (){ int[] a = { 1, 4, 5, 8 }; int N = a.Length; int[] b = { 1, 3, 4, 6, 7 }; int M = b.Length; // Function call Console.Write(min_sum(a, b, N, M)); }}// This code is contributed by hrithikgarg03188. |
Javascript
<script> // JavaScript code for the above approach// Function to return the// minimum absolute differencefunction min_sum(a,b,N, M){ // Sorting both the arrays a.sort(); b.sort(); let dp = new Array(M+1); for(let i=0;i<dp.length;i++) { dp[i] = new Array(N+1) } // Initialising the dp to high value for (let i = 0; i <= M; i++) { for (let j = 0; j <= N; j++) { dp[i][j] = 1e9; } } dp[0][0] = 0; // Iterating through each element // of the larger array b for (let i = 0; i < M; i++) { // Case 1. Where we are not taking // the element at ith index for (let j = 0; j <= N; j++) { dp[i + 1][j] = dp[i][j]; } // Case 2. When we have to take the // element at ith index for (let j = 0; j < N; j++) { dp[i + 1][j + 1] = Math.min(dp[i + 1][j + 1], dp[i][j] + Math.abs(a[j] - b[i])); } } return dp[M][N];}// Driver code let a = [1, 4, 5, 8]; let N = a.length; let b = [1, 3, 4, 6, 7 ]; let M = b.length; // Function call document.write(min_sum(a, b, N, M)); // This code is contributed by Potta Lokesh </script> |
2
Time complexity: O(N * M log N)
Auxiliary Space: O(N * M)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Find More to that Topic: geeksforgeeks.org/minimum-possible-sum-of-absolute-difference-of-pairs-from-given-arrays/ […]
… [Trackback]
[…] Read More here on that Topic: geeksforgeeks.org/minimum-possible-sum-of-absolute-difference-of-pairs-from-given-arrays/ […]
… [Trackback]
[…] Read More to that Topic: geeksforgeeks.org/minimum-possible-sum-of-absolute-difference-of-pairs-from-given-arrays/ […]
… [Trackback]
[…] Here you will find 12883 more Information to that Topic: geeksforgeeks.org/minimum-possible-sum-of-absolute-difference-of-pairs-from-given-arrays/ […]