Given Two Lists of Integers, Find Each Pair Within a Distance of Each Other < O(N^2)

Question

I have two sorted lists of integers. I would like to find all pairs of integers from the first and second list, respectively, that are within a certain distance of each other.

The naive approach is to check each pair, resulting in a O(N^2) time. I am sure there is a way to do it in O(N*logN) or maybe shorter.

In python, the naive O(N^2) approach is as follows:

def find_items_within(list1, list2, within):
    for l1 in list1:
        for l2 in list2:
            if abs(l1 - l2) <= within:
                yield (l1, l2)

Extra points for pythonic answers.

Application Note

I just wanted to point out the purpose of this little puzzle. I am searching a document and want to find all the occurrences of one term within a certain distance of another term. First you find the term vectors of both terms, then you can use the algorithms described below to figure out if they are within a given distance of each other.

Answer 1

There is no way to do it better then O(n^2) because there are O(n^2) pairs, and for within = infinity you need to yield all of them.

---

To find the number of these pairs is a different story, and can be done by finding the first index for each element e that suffices within-e < arr[idx]. The index idx can be found efficiently using binary search for example - which will get you O(nlogn) solution to find the number of these pairs.

It can also be done in linear time (O(n)), since you don't really need to do a binary search for all elements, after the first [a,b] range is found, note that for each other range [a',b'] - if a>a' then b>=b' - so you actually need to iterate the lists with two pointers and "never look back" to get a linear time complexity.

pseudo code: (for linear time solution)

numPairs <- 0
i <- 0
a <- 0
b <- 0
while (i < list1.length):
  while (a < i && list1[i] - list2[a] > within):
      a <- a+1
  while (b < list2.length && list2[b] - list1[i] < within):
      b <- b+1
  if (b > a):
      numPairs <- numPairs + (b-a)
  i <- i+1
return numPairs

(I made some fixes from the initial pseudo code - because the first one was aiming to find number of pairs within range in a single list - and not matches between two lists, sorry for that)

Answer 2

This code is O(n*log(n)+m) where m is the size of the answer.

def find_items_within(l1, l2, dist):
    l1.sort()
    l2.sort()
    b = 0
    e = 0
    ans = []
    for a in l1:
        while b < len(l2) and a - l2[b] > dist:
            b += 1
        while e < len(l2) and l2[e] - a <= dist:
            e += 1
        ans.extend([(a,x) for x in l2[b:e]])
    return ans

In the worst case, it is possible that m = n*n, but if the answer is just a small subset of all possible pairs, this is a lot faster.

Answer 3

Here something with the same interface as you have given:

def find_items_within(list1, list2, within):
    i2_idx = 0
    shared = []
    for i1 in list1:
        # pop values to small
        while shared and abs(shared[0] - i1) > within: 
            shared.pop(0)
        # insert new values 
        while i2_idx < len(list2) and abs(list2[i2_idx] - i1) <= within:
            shared.append(list2[i2_idx])
            i2_idx += 1
        # return result
        for result in zip([i1] * len(shared), shared):
            yield result

for item in find_items_within([1,2,3,4,5,6], [3,4,5,6,7], 2):
    print item

Not very beautiful but it should do the trick in O(N*M), where N is the length of list1 and M the list of shared pairs per Item (given that the elements dropped and appended to shared is constant on the average).

Answer 4

This seems to work:

from itertools import takewhile
def myslice(lst,start,stop,stride=1):
    stop = len(lst) if stop is None else stop
    for i in xrange(start,stop,stride):
        yield lst[i]

def find_items_within(lst1,lst2,within):
    l2_start = 0
    for l1 in lst1:
        try:
            l2_start,l2 = next( (i,x) for i,x in enumerate(myslice(lst2,l2_start,None),l2_start) if abs(l1-x) <= within )
            yield l1,l2
            for l2 in takewhile(lambda x:(abs(l1-x) <= within), myslice(lst2,l2_start+1,None)):
                yield l1,l2
        except StopIteration:
            pass


x = range(10)
y = range(10)
print list(find_items_within(x,y,2.5))

Answer 5

Depending on the distribution of the values in your lists, you might be able to speed things up by using binning: take the range in which all your values fall (min(A+B), max(A+B)), and divide that range into bins of the same size as the distance D you’re considering. Then, to find all pairs, you only need to compare values within a bin or within adjacent bins. If your values are split up between many bins, this is an easy way to avoid doing M*N comparisons.

Another technique that might be just as easy in practice: Do a sort of bounded linear scan. Maintain an index into list A and into list B, starting from the beginning. On each iteration, advance the index into list A (start with the first element), call this element A0. Then, advance the index into list B. Remember the last value of B that’s less than A0-D (this is where we’ll want to start for the next iteration). But keep moving forward while you’re finding values between A0-D and A0+D — these are the pairs you’re looking for. As soon as the values in B become greater than A0+D, stop this iteration and start the next one — advance one element further into A, and start scanning B from the last place where B was < A0-D.

If you have, on average, a constant number of nearby pairs per element, I think this should be O(M+N)?

Answer 6

This method uses a dictionary whose keys are possible values of list2, and whose values are a list of values of list1 that are within distance of that value of list2.

def find_items_within(list1, list2, within):
    a = {}
    for l1 in list1:
        for i in range(l1-within, l1+within+1):
            if i not in a:
                a[i] = []
            a[i].append(l1)
    for l2 in list2:
        if l2 in a:
            for l1 in a[l2]:
                yield(l1, l2)

The complexity for this one is kind of goofy. for a list1 of size M and a list2 of size N and a within of size W, it's O(log(M*W) * (M*W + N)). In practice I think it works pretty well for small W.

Bonus: this works on unsorted lists too.

Answer 7

You can find integers from list2 that are in [x - within, x + within] interval for all x from list1 in linear time (O(n)) using "scan line" technique (see How to Find All Overlapping Intervals and Sub O(n^2) algorithm for counting nested intervals?).

To enumerate corresponding intervals from list1 you need O(m) time where m is the number of intervals i.e., the overall algorithm is O(n*m):

from collections import namedtuple
from heapq import merge

def find_items_within(list1, list2, within):
    issorted = lambda L: all(x <= y for x, y in zip(L, L[1:]))
    assert issorted(list1) and issorted(list2) and within >= 0

    # get sorted endpoints - O(n) (due to list1, list2 are sorted)
    Event = namedtuple('Event', "endpoint x type")
    def get_events(lst, delta, type):
        return (Event(x + delta, x, type) for x in lst)
    START, POINT, END = 0, 1, 2 
    events = merge(get_events(list1, delta=-within, type=START),
                   get_events(list1, delta=within, type=END),
                   get_events(list2, delta=0, type=POINT))

    # O(n * m), m - number of points in `list1` that are 
    #               within distance from given point in `list2`
    started = set() # started intervals
    for e in events:  # O(n)
        if e.type is START: # started interval
            started.add(e.x) # O(m) is worst case (O(1) amortized)
        elif e.type is END: # ended interval
            started.remove(e.x)  # O(m) is worst case (O(1) amortized)
        else:  # found point
            assert e.type is POINT
            for x in started:  # O(m)
                yield x, e.x

To allow duplicate values in list1; you could add index for each x in Event and use a dictionary index -> x instead of the started set.