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)
.