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

Question

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.

In simplest case I'd use two nested loops to create all possible pairs, and something like a Set<Pair<Integer, Integer>> to store the pairs without repetitions. — 9000
– 9000, Commented Jun 21, 2015 at 2:55
That would time out on large N's pretty quickly I think, is there a faster way ? — WeirdAl
– WeirdAl, Commented Jun 21, 2015 at 4:34
2+12 ≤ 10? Has math changed? Do you mean S=13, with pairs (1,11), (1,12) and (2,11)? — outis
– outis, Commented Jun 23, 2015 at 17:54

jhostetler · Accepted Answer · 2015-06-23 07:43:34Z

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.

gnasher729 · Accepted Answer · 2015-06-23 16:15:22Z

Assume both A and B have a million members, and you have sorted A and B.

How many pairs can you form with A [0]? To find out, you add A [0] + B [0], A [0] + B [1], A [0] + B [2] etc. You stop when the result is too large, and then you know how many. Say A [0] + B [920178] is not too large, but A [0] + B [920179] is too large, then you can form 920179 pairs using A [0]. That method works because B is sorted.

How many pairs can you form with A [1]? Since A is sorted, A [0] <= A [1]. That means A [1] + B [920179] is too large. You search downward until you find for example that A [1] + B [920174] is not too large. This gives another 920175 pairs.

You repeat the same with A [2], A [3] up to A [999999]. So how long does this take? You examine a million values of A. You also examine at most a million values of B, because your search downward through B will end at B [0].

You'll have to be a bit careful at the ends of the arrays to avoid bugs in your code.

Stack Exchange Network

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

2 Answers 2

Your Answer

Hot Network Questions

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

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Related

Hot Network Questions