Intersection Algorithms

Given two lists [T], the following algorithm finds the intersection (values common to both lists) in O(min(m, n)) time and O(min(m,n)) space provided that:

• The two lists are sorted.
• T is orderable and comparable.
• Both lists do not contain repeat elements.

def intersection(A, B):
    a = len(A)
    s = 0
    R = []
    for n in B:
        for i in range(s, a):
            c = A[i]
            if n < c:
                break
            s += 1
            if n == c:
                R.append(n)
                break
        if s == a:
            break
    return R

Another algorithm for when intersections should be found in place. This modifies A. Most of the ugliness from the code stems from the fact that it is hard to iterate backwards in Python. Again all conditions from the first algorithm need to be satisfied. However:

• Space complexity is essentially O(1)
• Time complexity is higher, at worse O(max(n,m)) due to the additional deletes.

def intersection(A, B):
    b = len(B) - 1
    a = len(A) - 1

    # Find intersections, and set a to be the index
    # where the algorithm should search from
    for i in range(b, -1, -1):
        n = B[i]
        for j in range(a, -1, -1):
            c = A[j]
            if n > c:
                break
            a -= 1
            if n == c:
                break
            del A[j]

    # everything below a is not included in the other
    # set, so delete
    for j in range(a, -1, -1):
        del A[j]
    return A

Both algorithms exploit the fact that the lists are already sorted, and break from the inner loop early to avoid a full scan whenever it makes sense to avoid O(mn). It is possible to use a binary search instead of the linear scan to determine the index.

However, that would give a worse time complexity should the lists have very tighly clustered values: linear search is at worse, O(n) but Ω(1). However a binary search is almost always O(log n). Case in point:

Easy to find 1 in [1,2,3,4,5,6,7,8] using linear search. However a binary search needs ~3 steps.