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

**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: **

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
import java.util.*; public class FindLeastCommonSet<T> { private Map<T, T> parent = new HashMap<>(); private Map<T, Integer> rank = new HashMap<>(); private Map<T, Set<T>> res= new HashMap<>(); //Time O(nlogn), n is total elements, Space O(n) for maps public void makeSet(T[][] input) { for (T[] row : input) { for(T t: row ) { parent.put(t, t); rank.put(t, 0); } for(int i = 0; i < row.length-1; i++) { union(row[i], row[i+1]); } } groupSets(); } //Time O(logn) , Space O(logn) for recursion stack frame public T find(T k){ if (parent.get(k) != k) { parent.put(k, find(parent.get(k))); } return parent.get(k); } //Time O(logn) , Space O(logn) for recursion stack frame public void union(T a, T b){ T x = find(a); T y = find(b); if (x == y) { return; } if (rank.get(x) > rank.get(y)) { parent.put(y, x); } else if (rank.get(x) < rank.get(y)) { parent.put(x, y); }else{ parent.put(x, y); rank.put(y, rank.get(y) + 1); } } //Time O(nlogn), Space O(n) for maps private void groupSets(){ for (T i : parent.keySet()) { T p = find(i); res.putIfAbsent(p, new HashSet<T>()); res.get(p).add(i); } } //Time O(nlogn), Space O(n) for maps public void printSets(T[][] input) { if (parent.isEmpty()) makeSet(input); System.out.println(res); } //Time O(nlogn), Space O(n) for maps and PriorityQueue public T[] findLeastCommonGroup(T[][] input) { if (parent.isEmpty()) makeSet(input); PriorityQueue<Set<T>> pq = new PriorityQueue<>((a,b) -> a.size()-b.size()); pq.addAll(res.values()); Set<T> least = pq.poll(); for (T[] row: input) { if(least.contains(row[0])) return row; } return null; } public static void main(String[] args){ FindLeastCommonSet<Character> ds = new FindLeastCommonSet<>(); Character[][] input = {{'a','b','c','d'}, {'a','b','f','g'}, {'a','b','h','i'}, {'j','k','l','m'}}; Character[] b = ds.findLeastCommonGroup(input); System.out.println("Find least common set: " + Arrays.toString(b)); } } |

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

Download FindLeastCommonSet.java

Java coding interview pocket book insight

Minimum Spanning Tree with union find (GitHub)