Three-way set Disjointness

Question

this is a question from my practice problems for an upcoming test. I was hoping to get help in finding a more efficient solution to this problem. Right now, I know I can solve this type of problem just by using 3 simple for loops, but that would be O(N^3).

Furthermore, I believe that somehow incorporating binary search will be the best way, and give me the O(log n) in the answer that I'm looking for. Unfortunately, I'm kind of stuck.

The three-way set disjointness problem is defined as follows: Given three sets of items, A, B, and C, they are three-way disjoint if there is no element common to all three sets, ie, there exists no x such that x is in A, B, and C.

Assume that A, B, and C are sets of items that can be ordered (integers); furthermore, assume that it is possible to sort n integers in O(n log n) time. Give an O(n log n) algorithm to decide whether the sets are three-way set disjoint.

Thanks for any assistance

Answer 1

The question statement has given obvious hint on how to solve the problem. Assuming the 3 sets are mathematical sets (elements are unique within each set), just mix 3 sets together and sort them, then traverse the list linearly and search whether there are 3 instances of the same item. The time complexity is dominated by sorting, which is O(n log n). The auxiliary space complexity is at most O(n).

Another solution is to use hash-based map/dictionary. Just count the frequency of the items across 3 sets. If any of the items has frequency equal to 3 (this can be checked when the frequency is retrieved for update), the 3 sets are not 3-way disjoint. Insertion, access and modification can be done in O(1) amortized complexity, so the time complexity is O(n). The space complexity is also O(n).

Answer 2

If complexity is the constraint (and neither space or the constant term are), this can be solved in O(n). Create two bitmaps, mapping integers from A to the first and integers from B to the second. Then traverse the third (C) until you exhaust, or you find an entry where bitmapA(testInt) and bitmapB(testInt) are both set.

Answer 3

We can solve this problem with o(n). This is possible if we use Set data structure and consider initial capacity and load factor into consideration.

public static boolean checkThreeWaySetDisjointness(Set<Integer> a, Set<Integer> b, Set<Integer> c)
    {
        int capacity = Math.round((a.size() + b.size()) / 0.75f) + 1;
        Set<Integer> container = new HashSet<Integer>(capacity);
        container.addAll(a);
        for (int element : b)
        {
            if (!container.add(element))
            {
                if (c.contains(element))
                {
                    return false;
                }
            }
        }
        return true;
    }

We are creating new Set container because if we start adding directly in any of existing Set a/b/c, once its capacity of 75 % of actual size is reached, internally java will create new Hashset and copies entire existing Set in it. This overhead will have complexity of O(n). Hence we are creating here new HashSet of size capacity which will ensure there will not be an overhead of copying. Then copy entire Set a and then go on adding one by one element from Set b. In Java , if add() returns false means element already exists in current collection. If yes, just check for the same in third Set c. Method add and contains of HashSet have complexity of O(1) so this entire code runs in O(n).