Find a pair of pairs with no intersection

Question

Given a set of n pairs of integers, is there a fast way to determine if there exists two pairs (x₁, y₁) and (x₂, y₂) so that the intersection of the sets {x₁, y₁} and {x₂, x₂} is empty?

For example, {(0,1), (0,2), (2,1), (3,2)} has {(0,1), (3,2)} as an answer. However {(0,1), (0,2), (2,1)} has no such pair of pairs.

In Python, you could just try all pairs as follows.

l = [(0,1), (0,2), (2,1), (3,2)]
print  [pairs for pairs in itertools.combinations(l, 2)
    if not (set(pairs[0]) & set(pairs[1]))]

This approach takes O(n²) time. Can you get something closer to linear time?

Answer 1

The following algorithm should work in O(n) time. It's based on the following observation: if you have a pair {a, b}, then every other pair

1. Doesn't include a or b, or
2. Includes at least one of a or b.

If you choose any set {a, b} and categorize each other set into one of these five categories, note that if you get anything in Case 1, then you're done and you know such a pair exists. So the only interesting case is when every other set falls into case 2. When this happens, we can call the two groups the "A" group and the "B" group (for sets that match a and for sets that match b).

Once you have the A group and the B group, you know that no two A sets can be the pair you want, no two B sets can be the pair you want, and the set {a, b} can't be part of the pair you want. The only option is if you can take something from the A group and pair it with something from the B group. This only happens if some non-A component from the A group doesn't match any non-B component from the B group. You can check this in O(n) by building a hash table holding the non-A components of the A group and then checking for each element of the B group whether its non-B component is in the hash set.

To summarize, the algorithm is

• Choose a pair {a, b}.
• For each other pair {c, d}:
  • If {a, b} and {c, d} are disjoint, you're done.
  • Otherwise, if {a, b} = {c, d}, discard {c, d}.
  • Otherwise, put {c, d} into either the A group if it includes a or the B group if it includes b.
• If either the A group or B group is empty, no pair exists. Return false.
• For each element of the A group, add the non-a component of the pair to a hash set.
• Return true if any element of the B group has a non-b component not in the hash set and false otherwise.

This runs in time O(n) and uses O(n) extra memory.

Hope this helps!

Answer 2

Before reading this read templatetypedef answer.

^{I'll personally hunt whoever upvotes this answer without upvoting his answer, since he did all the work}

---

Here's a (self-explanatory) python implementation of the algorithm defined in templatetypedef answer:

def exists_pair(seq):
    if len(seq) < 2:
        return False
    a, b = seq[0]  # could be: seq.pop() if modifications are allowed
    a_group = set()
    b_group = set()
    for c, d in seq:
        if not ({a,b} & {c,d}):
            return True
        elif {a,b} == {c,d}:
            continue
        elif a in {c,d}:
            a_group.add(c if c != a else d)
        else:
            b_group.add(c if c != b else d)

    if not a_group:
        return False

    # b_group - a_group: elements of b_group that do not appear in a_group
    return bool(b_group - a_group)

There's no need to check for an empty b_group because the result of b_group - a_group is always a subset of b_group. If b_group is empty the result will always be empty and bool of empty set is False, which is correct.