How to find the maximum number of pairs having difference less than a particular value?

2
votes

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.

1
c++algorithm
Your 2nd sentence is not clearly written. Do you mean: "I have to find the number of unique pairs that have absolute difference less than or equal to a given value." – Karlis Olte
Yes, but the if the numbers are used once to form a pair, they cant be used again. – John Lui
I'm voting to close this question as off-topic because this is an on-going competition which will be finished in a day. – Salvador Dali

1 Answers

0
votes

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:
    1. If a pair is found insert it into your list. Increase both iterators.
    2. 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