Find least common set – Outlier set

Given an array of sets, find the least common set. The least common set is also an outlier set, that has least in common with other sets. There are different ways to find the least common set. One ways is to use union-find to make all elements in a disjoint set. From the disjoint set, you can find a subset with the more elements than others. Then you scan each input set and count how many elements in the popular subset. The one with the smallest counts is the least common set.

least common set

There is another simple way. You use a map to store all counts for each elements. The key is element, the value is the count. You reset the map’s value, if the count is larger than 1, reset the count to 1. If the count is 1, reset to 0. Then you scan each input set to sum up the counts in the map. The set with the smallest counts is the least common set.

Google Interview Question :
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.




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

O Notation:
Time complexity: O(m*n*),
m is number of input sets, n is average number elements in each set
Space complexity: O(m*n))

Download FindLeastCommonSet.js
Minimum Spanning Tree with union find (GitHub)

Comments are closed