Calculating distance between element of two arrays

Question

I have 2 arrays A[] and B[] with n elements each , I want to calculate the difference between each element of A array to the element of B array, and output is the set of Elements with difference less than x0 (some value).

For ex : A =[1,2,3] B=[2,3,4]
I want "1-2","1-3","1-4","2-3" ...

say x0 = 2, So the output be ([1,2],[1,3],[2,3]...).

I'm using the brute force approach ,taking each element of array A and subtracting with B's element which has time complexity of O(n^2). Can anyone suggest better approach ?

Elisha · Answer 1 · 2018-04-11T18:12:05.957

The complexity of this problem is output-sensitive, meaning, if all possible pairs match, then the alogirhtm must run O(n^2) time. Assuming the output is smaller then O(n*log(n)), the following python code runtime is O(n*log(n)):

from bisect import bisect_left, bisect_right
from itertools import repeat

arr1 = [1, 2, 3]
arr2 = sorted([2, 3, 4, 5])

d = 1

result = []
for item in arr1:
    left, right = bisect_left(arr2, item - d), bisect_right(arr2, item + d)
    result += zip(repeat(item), arr2[left:right])

The code above sorts one of the arrays, and then searches the other one items from in the sorted one. This requires O(n*log(n)) time for sorting one of the arrays, and then O(log(n)) for bisecting the array for each search.

score 0 · Answer 2 · answered Apr 12 '18 at 07:14

Find pairs: (Ai, Bi) where Ai - Bi < X0,

Now,

   Ai - Bi < X0,
=> Ai - X0 < Bi

That means that any element in B which value greater than (Ai - X0) would result in Ai - Bi < X0

So basically, You have to search for elements in B which are greater than some other value, say P.

You can easily search elements in sorted array in O(lgN) time. In this case, you will need modified binary search which finds index of values greater than given value.

Here is how you can achieve that: (Click Here)

Here is the complete algorithm:

getPairs(A,B,X0)
    sort(B)
    pairs = []
    for each element Ai in A do:
        P = Ai - X0
        index = modifiedBinarySearch(B, P)
        while ( index < B.length ) do
            pairs.push( { Ai, Bindex } )
            index++
        done
    done
    return pairs
done

Time Complexity:

Sorting array of N elements:        O(NlgN)
Iterating over array of N elements: O(N)
The inner while loop:               O(N)

Thus, overall complexity:           O(NlgN)

If you are not sure about how inner while loop takes, O(N), let me know in comments.

Calculating distance between element of two arrays

2 Answers2