I am given two arrays (can contain duplicates and of same length) containing positive integers. I have to find the maximum number of pairs that have absolute difference less than equal to a particular value (given) when numbers can be used only once from both the arrays.

For example:

```
arr1 = {1,2,3,4}
arr2 = {8,9,10,11}
diff = 5
```

Then, possible pairs are (3,8), (4,8). That is, only two such possible pairs are there.

Output should be 2.

Also, I can think of an algo for this in O(n^2). But, I need something better. I thought of hash maps (won't work because arrays contain duplicates), thought of sorting the arrays in descending and ascending order, wasn't really able to move forward from there.

# Best How To :

The usual idea is to loop over *sorted* ranges. This, you can bring down the brute-force `O(N^2)`

effort to usually `O(N log N)`

.

Here is an algorithm for that in pseudo code (maybe I'll update later with real C++ code):

- Sort both arrays
- Loop over both simultaneously with two iterators:
- If a pair is found insert it into your list. Increase both iterators.
- Otherwise, increase the indicator pointing to the smaller element.

In total, this is dominated by the sort which on average takes `O(N log N)`

.

Here is the promised code:

```
auto find_pairs(std::vector<int>& arr1, std::vector<int>& arr2, int diff)
{
std::vector<std::pair<int,int> > ret;
std::sort(std::begin(arr1), std::end(arr1));
std::sort(std::begin(arr2), std::end(arr2));
auto it1= std::begin(arr1);
auto it2= std::begin(arr2);
while(it1!= std::end(arr1) && it2!= std::end(arr2))
{
if(std::abs(*it1-*it2) == diff)
{
ret.push_back(std::make_pair(*it1,*it2));
++it1;
++it2;
}
else if(*it1<*it2)
{
++it1;
}
else
{
++it2;
}
}
return ret;
}
```

It returns the matching elements of the two vectors as a vector of `std::pairs`

. For your example, it prints

```
3 8
4 9
```

DEMO