Introduction to Union Find
Let’s go over the Union Find pattern, its real-world applications and some problems we can solve with it.
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:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.