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> |
Â
Â
Output
2
Â
Time complexity: O(N * M log N)
Auxiliary Space: O(N * M)
Â
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
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/ […]