6

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?

10
  • 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 '20 at 13:47
  • 1
    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.
    – Mandrill
    Nov 28 '20 at 17:36
  • It helps when the title isn’t misleading. Nov 28 '20 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.
    – rwong
    Nov 29 '20 at 8:20
  • 2
    @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 '20 at 21:08
3

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.

3
  • 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 '20 at 1:11
  • O(..) is worst case, so "usually O(...)" should be one of the other ones. Omega? Nov 29 '20 at 12:28
  • 1
    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)
    – Jasmijn
    Nov 29 '20 at 14:32
3

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.

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

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)
3
  • 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.
    – Jasmijn
    Nov 29 '20 at 14:17
  • How you can create quadratic memory in linear time?
    – RiaD
    Nov 30 '20 at 8:52
  • That asssumes that the dict.add method is constant. Nov 30 '20 at 11:07
0

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.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.