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

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 not in tuple2 and tuple1 not in tuple2:
return True
return False
``````

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

• Really unclear why I've got multiple downvotes. I have an interesting problem, I spent hours trying to find a solution, I posted the solution even though I feel its suboptimal, and while I wait for a better solution to accept I keep getting downvotes. Can someone please explain the reasoning here? Nov 28, 2020 at 13:47
• Mad because they don't know the answer? Only explanation I can find. Or maybe they think this is a homework question since it is not clear how would it be useful. Nov 28, 2020 at 17:36
• It helps when the title isn’t misleading. Nov 28, 2020 at 23:59
• @TheEnvironmentalist What are the typical sizes of these sets? What is the maximum total number of individual items? I am thinking whether bit-mask testing can be used to accelerate the search. It wouldn't alter the `O(n^2)` time complexity, though. Nov 29, 2020 at 8:20
• @TheEnvironmentalist I believe you’ll find, on the whole, that the brutally harsh criticism this site is famous for is not due a lack of familiarity with computational complexity. But rather due to a completely uncharitable insistence on good communication. TL;DR few edit when they can just downvote. So proofread. Nov 29, 2020 at 21:08

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.

• I think I came up with your second answer! Definitely going to look into k-d trees now and see if anyone posts anything else. This has turned into a really fun puzzle! Nov 28, 2020 at 1:11
• O(..) is worst case, so "usually O(...)" should be one of the other ones. Omega? Nov 29, 2020 at 12:28
• Big O isn't worst case, it can be used for worst case, average case, best case, etc. It provides an upper bound for the growth of a function, but that function can be a mapping from input size to the best case run-time of a function. Also, they're probably referring to amortized run time being O(1) (even in the worst case) Nov 29, 2020 at 14:32

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.

• Note that you don't need to calculate anything in advance, everything is linear and can be done right when you are asking.
Dec 1, 2020 at 0:06

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 not in directory:
directory[tup] = set()

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

for tup in list2:
if tup not in directory and tup not in directory
or tup in directory and tup not in directory[tup]:
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 not in directory and tup not in directory
or tup in directory and tup not in directory[tup]
or tup in directory and tup not in directory[tup]:
return True
return False

# Algorithm skips by (a, b) and (a, h) and returns True on (k, a)
``````
• Counterexample: `has_unique_pair([(a, b), (c, d)], [(a, b)])` returns false but should return true because `(c, d), (a, b)` is a valid unique pair. Nov 29, 2020 at 14:17
• How you can create quadratic memory in linear time?
Nov 30, 2020 at 8:52
• That asssumes that the dict.add method is constant. Nov 30, 2020 at 11:07

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.