Difference of elements of 2 sorted arrays within given interval

Question

Let us assume that we have 2 sorted arrays A and B of integers and a given interval [L,M] . If x is an element of A and y an element of B ,our task is to find all pairs of (x,y) that hold the following property: L<=y-x<=M. Which is the most suitable algorithm for that purpose?

So far ,I have considered the following solution: Brute force. Check the difference of all possible pairs of elements with a double loop .Complexity O(n^2).

A slightly different version of the previous solution is to make use of the fact that arrays are sorted by not checking the elements of A ,once difference gets out of interval .Complexity would still be O(n^2) but hopefully our program would run faster at an average case.

However ,I believe that O(n^2) is not optimal .Is there an algorithm with better complexity?

Answer 1

Here is a solution.

Have a pointer at the beginning of each array say i for array A and j for array B.

Calculate the difference between B[j] and A[i].

If it is less than L, increment the pointer in array B[], i.e increment j by 1

If it is more than M, increment i, i.e pointer of A.

If the difference is in between, then do the following:

• search for the position of an element whose value is B[j]-A[i]-L or the nearest element whose value is lesser than (B[j]-A[i])-L in array A. This takes O(logN) time. Say the position is p. Increment the count of (x,y) pairs by p-i+1

• Increment only pointer j

My solution only counts the number of possible (x,y) pairs in O(NlogN) time

For A=[1,2,3] and B=[10,12,15] and L=12 and M=14, answer is 3.

Hope this helps. I leave it up to you, to implement the solution

Edit: Enumerating all the possible (x,y) pairs would take O(N^2) worst case time. We will be able to return the count of such pairs (x,y) in O(NlogN) time. Sorry for not clarifying it earlier.

Edit2: I am attaching a sample implementation of my proposed method below:

def binsearch(a, x):

    low = 0
    high = len(a)-1
    while(low<=high):
        mid = (low+high)/2
        if a[mid] == x:
            return mid
        elif a[mid]<x:
            k = mid
            low = low + mid
        else:
            high = high - mid

    return k

a = [1, 2, 3]
b = [10, 12, 15, 16]
i = 0
j = 0

lenA = len(a)
lenB = len(b)

L = 12
M = 14
count = 0 
result = []
while i<lenA and j<lenB:
    if b[j] - a[i] < L:
        j = j + 1
    elif b[j] - a[i] > M:
        i = i + 1
    else:
        p = binsearch(a,b[j]-L)
        count = count + p - i + 1
        j = j + 1

print "number of (x,y) pairs: ", count

Answer 2

Because it's possible for every combination to be in the specified range, the worst-case is O([A][B]), which is basically O(n^2)

However, if you want the best simple algorithm, this is what I've come up with. It starts similarly to user-targaryen's algorithm, but handles overlaps in a simplistic fashion

Create three variables: x,y,Z and s (set all to 0)
Create a boolean 'success' and set to false
Calculate Z = B[y] - A[x]
if Z < L
    increment y
if Z >= L and <= M
    if success is false
        set s = y
        set success = true
    increment y
    store x,y
if Z > M
    set y = s   //this may seem inefficient with my current example
                //but you'll see the necessity if you have a sorted list with duplicate values)
                //you can just change the A from my example to {1,1,2,2,3} to see what I mean
    set success = false

an example: A = {1,2,3,4,5} B = {3,4,5,6,7} L = 2, M = 3

In this example, the first pair is x,y. The second number is s. The third pair is the values A[x] and B[y]. The fourth number is Z, the difference between A[x] and B[y]. The final value is X for not a match and O for a match

0,0 - 0 - 1,3 = 2 O
    increment y
0,1 - 0 - 1,4 = 3 O
    increment y
0,2 - 0 - 1,5 = 4 X
    //this is the tricky part. Look closely at the changes this makes
    set y to s
    increment x
1,0 - 0 - 2,3 = 1 X
    increment y
1,1 - 0 - 2,4 = 2 O
    set s = y, set success = true
    increment y
1,2 - 1 - 2,5 = 3 O
    increment y
1,3 - 1 - 2,6 = 4 X
    set y to s
    increment x
2,1 - 1 - 3,4 = 1 X
    increment y
2,2 - 1 - 3,5 = 2 O
    set s = y, set success = true
    increment y
2,3 - 2 - 3,6 = 3 O
... and so on