Find Least common set with union find – code

When we have number of sets, and need to group them into joint and disjoint-sets, union–find is the algorithm to go. This question is one step further, we need to find least common set with union find. What is union find? Union-find is to stores data in non-overlapping sets (ie groups). It achieve this by using two operations union and find.
Union connect two elements by put them into a tree structure, making one as parent of the other. One tree structure can be seen as one set, all elements in the tree are associated with this root. Find is to find the root of the tree for a given element. From the root, we can find out which set this element belongs. We use HashMap to store parent info for all elements in joint and disjoint sets.

The time complexity of union-find is O(n) (ie traversal of tree). We can optimize it by using union by rank, meaning we attach smaller depth tree under the root of the deeper tree. This improves the time complexity to O(logn). Again HashMap is used to store rank info for all elements.

Now it is the time to find least common set. First, use PriorityQueue to sort all disjoint sets by their lengths. Then scan each set in the input. If an input set has element in shortest set, that’s the least common set. Here are the implementation of find least common set with union find.

Google Interview Question (CareerCup):
Given an array of sets find the one that does not belong: example: [[a,b,c,d], [a,b,f,g], [a,b,h,i], [j,k,l,m]]
output: [j,k,l,m]
We can see above that the first three sets have a subset [a,b,c] and the last one does not. Note: There may be a case where the outlier set does have elements contained in the input group. In this case we have the find the set that has the least in common with the other sets.

Java Code:

Output:
Find least common set: [j, k, l, m]

O Notation:
Time complexity: O(nlogn), n is total elements in all sets
Space complexity: O(n)


Actionable:
Download FindLeastCommonSet.java
The complete list of coding interview questions
Minimum Spanning Tree with union find

Comments are closed