Java – Find the maximum number of pairs of numbers that are in a range, between two arrays

algorithmsarrayjava

Lets say I have two arrays A and B 

A = {1,2,3}
B = {12,11,67}
and have max sum value S = 10

How many maximum number of unique pairs can be formed between the two arrays who's sum is less than or equal to S.

For e.g., the two possible values here are [1,11] [2,12] hence the answer is 2. If there are none, the answer is 0.

My solution was to sort both the arrays and then go do 

 if((Math.abs(A[i]-B[i]))<=S)
                 {
                 ans++;
             }

Although it works for this case, clearly this is incorrect.

Best Answer

The key to doing this efficiently is exploiting the fact that if a1 < a2, then pair(a2) \subseteq pair(a1), where pair(a) = {b \in B : a + b <= S}. Example Java code:

Arrays.sort( A );
Arrays.sort( B );
int count = 0;
int j = B.length - 1;
for( int i = 0; i < A.length; ++i ) {
    while( j >= 0 ) {
        if( A[i] + B[j] <= S ) {
            break;
        }
        --j;
    }
    if( j < 0 ) {
        break;
    }
    count += (j + 1);
}

This code assumes there are no duplicates in A or B. The dominant operation is the O(n log n) sort. The loop traverses each list once, so the overall complexity is O(n log n + 2n) which is in O(n log n). If there are duplicates they can be removed from the sorted lists in linear time.

Related Topic