Is there an algorithm that performs better than O(n^2) for this unique pair tuple problem?

Question

I'm trying to figure out if it's possible to have an algorithm that solves a certain problem in better than O(n^2) time.

Specifically, I'm looking for an algorithm that, given two lists of two-tuples (e.g. one could be [(a, b), (c, d), (e, f)]), figures out if there exists any pairs of tuples, one from each list, that don't share any common elements. Note that I don't actually need the pair itself if one exists, just to figure out whether or not such a pair exists.

Let's say these are our two lists:

list_one = [(a, b), (a, d), (a, f), (a, h), (f, h)]
list_two = [(k, a), (a, b), (a, h)]

In this case, there are exactly two such pairs, both containing the last tuple from list_one: [(f, h), (k, a)] and [(f, h), (a, b)]. Every other pair of tuples shares a in common, which violates the "no common elements" criterion.

Here's the first algorithm I came up with, but it's O(n^2), and I'm trying to figure out if it's possible to do better. I'm using Python 3 type annotation for improved readability:

from typing import List, Tuple

def has_unique_pair(list1: List[Tuple[int, int]], list2: List[Tuple[int, int]]):
    for tuple1 in list1:
        for tuple2 in list2:
            if tuple1[0] not in tuple2 and tuple1[1] not in tuple2:
                return True
    return False

Is better than O(n^2) time possible?

Answer 1

The more context, the easier this kind of thing.

If we can participate in the creation of the lists, they could be stored in a more organized data structure.  For example:

• the individual elements in the tuple sorted so that always (a,b) instead of (b,a).
• for the first list, use a hashtable for the first element, which contains a hash table for the second, then search each element of the 2nd list in the data structure representing the first.  Inserting into a hash table is usually O(1), done for N elements: O(N), same for searching each element of list 2 in data structure for list 1: O(N).

Oversimplified, of course.  There are also k-d trees that index multiple dimensions.

Answer 2

So, for the second list, create dictionary d[x]=number of pairs where element X is present as well as e[x, y] = number of pairs where both X and y are present.

Now for each element (a,b) of the first sequence you need to find if it's possible to get an element from the second list which it doesn't intersect. But we can count number of elements it intersect with! Due to inclusion-exclusion principle it's d[a]+d[b]-e[a,b] if this number of elements is less than length of the second list, then the answer is there is a good pair.

The solution is O(N) on average if you use hashmap or O(n log n) worst case if you use trees for a map.

Answer 3

I think I found one with O(n) time complexity but O(n^2) space complexity in the worst case, but I'm definitely interested to know if there's a better one, and I'm not going to accept my own answer unless no one posts a better answer:

from typing import List, Tuple


def has_unique_pair(list1: List[Tuple[int, int]], list2: List[Tuple[int, int]]):
    directory = {}
    for tup in list1:
        if tup[0] not in directory:
            directory[tup[0]] = set()

        directory[tup[0]].add(tup[1])

        if tup[1] not in directory:
            directory[tup[1]] = set()

        directory[tup[1]].add(tup[0])
    
    for tup in list2:
        if tup[0] not in directory and tup[1] not in directory
           or tup[0] in directory and tup[1] not in directory[tup[0]]:
            return True
    return False

Given the sample lists in the question (elements of list_two reordered for clarity):

list_one = [(a, b), (a, d), (a, f), (a, h), (f, h)]
list_two = [(a, b), (a, h), (k, a)]

Here's what this would look like:

directory = { a: set(b, d, f, h),
              b: set(a),
              d: set(a),
              f: set(a, h),
              h: set(a, f)
            }

for tup in [(a, b), (a, h), (k, a)]:
    if tup[0] not in directory and tup[1] not in directory
       or tup[0] in directory and tup[1] not in directory[tup[0]]
       or tup[1] in directory and tup[0] not in directory[tup[1]]:
        return True
return False

# Algorithm skips by (a, b) and (a, h) and returns True on (k, a)

Answer 4

There are 676 permutations ‘(a,a)...(z,z)’. Allocate a 676 bit bitmap for list one called ‘listOneOccursAtLeastOnce’ (‘bm1a’). Allocate a similar bitmap called ‘listOneOccursMoreThanOnce’ (‘bm1b’). Do the same for list two (‘bm2a’ and ’bm2b’).

Initialize all bits to zero.

Step through list one. Read the corresponding bit in ’bm1a’.

If the bit is zero set to one because we have seen the permutation at least once.

If the bit is one set the corresponding bit in ‘bm1b’ to one because we have seen it more than once.

XOR ‘bm1a’ and ‘bm1b’. Any bits that are set to one represent a unique tuple.

List two can be treated similarly.

Likewise the final logic.

Time is O(n). Space is constant based on the range of possible tuples. Engineering judgement is required, tuples of double precision floating point values is not amenable to this approach. ASCII characters are.