Maximizing Unique Pairs from two arrays in C++

Problem statement

Given two arrays of equal size N, form maximum number of pairs by using their elements, one from the first array and second from the second array, such that an element from each array is used at-most once and the absolute difference between the selected elements used for forming a pair is less than or equal to a given element K.

Example

If input is −

arr1[] = {3, 4, 5, 2, 1}

arr2[] = {6, 5, 4, 7, 15}

and k = 3 then we can form following 4 pairs whose absolute difference is less than or equal to 3 −

(1, 4), (2, 5), (3, 6), (4, 7)

Algorithm

We can use recursive approach to solve this problem

• Sort both the arrays
• Compare each element of the first array with each element of the second array for the possible pair, if it’s possible to form a pair
• Continue to check for the next possible pair for the next element of the first array.

Example

Let us now see an example −

 Live Demo

#include <bits/stdc++.h> using namespace std; int getMaxUniquePairs(int *arr1, int *arr2, int n, int k) {    sort(arr1, arr1 + n);    sort(arr2, arr2 + n);    bool visited[n];    memset(visited, false, sizeof(visited));    int pairCnt = 0;    for (int i = 0; i < n; ++i) {       for (int j = 0; j < n; ++j) {          if (abs(arr1[i] - arr2[j]) <= k &&          visited[j] == false) {             ++pairCnt;             visited[j] = true;             break;          }       }    }    return pairCnt; } int main() {    int arr1[] = {3, 4, 5, 2, 1};    int arr2[] = {6, 5, 4, 7, 15};    int n = sizeof(arr1) / sizeof(arr1[0]);    int k = 3;    cout << "Maximum unique pairs = " << getMaxUniquePairs(arr1, arr2, n, k) << endl;    return 0; }

Output

Maximum unique pairs = 4