I'm trying to figure out if it's possible to have an algorithm that solves a certain problem in better than
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
[(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 not in tuple2 and tuple1 not in tuple2: return True return False
Is better than
O(n^2) time possible?