Introduction to Union Find
Explore the union find pattern to group elements into unique sets based on properties, using efficient operations like union and find. Understand key optimizations such as union by rank and path compression to reduce time complexity. This lesson helps you solve graph and connectivity problems common in coding interviews, preparing you to tackle tasks involving connected components and set combinations.
We'll cover the following...
About the pattern
The union find pattern is used to group elements into sets based on a specified property. Each set is nonoverlapping, that is, it contains unique elements that are not present in any other set. The pattern uses a disjoint set data structure, such as an array, to keep track of which set each element belongs to.
Each set forms a tree data structure and has a representative element that resides at the root of the tree. Every element in this tree maintains a pointer to its parent. The representative’s parent pointer points to itself. If we pick any element in a set and follow its parent pointers, we’ll always reach the set representative.
The pattern is composed of two operations performed on the disjoint data structure:
find(v): Finds the representative of the set that contains v.
union(v1, v2): Merges the sets containing v1 and v2 into one.
Here is how the union find pattern uses these operations to form and extract information from sets of elements:
Note: In the above illustration, we skipped the
union(3,4)function to demonstrate how trees of heights greater thancan be merged.
For now, the worst-case time complexity of this approach is