Using Union Find Pattern
1. Understanding Union Find Technique
The Union-Find (also known as Disjoint Set) data structure is used to manage a collection of disjoint sets. It supports two primary operations:
find: Determines which set a particular element belongs to.union: Merges two sets into one.
This structure is particularly useful for problems involving connectivity, such as determining if two nodes are connected in a graph or grouping elements based on some equivalence relation.
| Operation | Description | Time Complexity (Amortized) | Space Complexity |
|---|---|---|---|
| find(x) | Returns the root of the set containing x | O(α(n)) | O(n) |
| union(x, y) | Merges the sets containing x and y | O(α(n)) | O(n) |
Example: Basic Union-Find Implementation
class UnionFind {
constructor(size) {
this.parent = Array.from({ length: size }, (_, i) => i);
this.rank = new Array(size).fill(0);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // Path compression
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
// Union by rank
if (this.rank[rootX] < this.rank[rootY]) {
[rootX, rootY] = [rootY, rootX];
}
this.parent[rootY] = rootX;
if (this.rank[rootX] === this.rank[rootY]) {
this.rank[rootX]++;
}
}
}
}
// Example usage:
const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(2, 3);
console.log(uf.find(0) === uf.find(1)); // true
console.log(uf.find(0) === uf.find(2)); // false
Note: Path compression and union by rank are optimizations that significantly improve performance, reducing the time complexity to nearly constant.
2. Implementing Find Operation
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| find(x) | Returns the root of the set containing element x | O(log n) amortized with path compression | O(1) |
| findWithPathCompression(x) | Find operation with path compression optimization | O(α(n)) amortized where α is the inverse Ackermann function | O(1) |
Example: Basic Find Implementation
class UnionFind {
constructor(n) {
this.parent = Array.from({length: n}, (_, i) => i);
this.rank = new Array(n).fill(0);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // Path compression
}
return this.parent[x];
}
}
const uf = new UnionFind(5);
console.log(uf.find(2)); // Output: 2 (root of element 2)
Note: Path compression makes subsequent operations faster by making the tree flatter.
3. Implementing Union Operation
| Operation | Description | Time Complexity | Implementation |
|---|---|---|---|
| union(x, y) | Merges the sets containing elements x and y | O(log n) amortized with path compression | |
Example: Union Operation in Action
const parent = [0, 1, 2, 3, 4];
const rank = [0, 0, 0, 0, 0];
function find(x) {
if (parent[x] !== x) {
parent[x] = find(parent[x]); // Path compression
}
return parent[x];
}
function union(x, y) {
const rootX = find(x);
const rootY = find(y);
if (rootX !== rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
// Example usage:
union(1, 2);
union(3, 4);
union(2, 4); // Merges sets {1,2} and {3,4}4. Detecting Cycle in Undirected Graph
The Union-Find (Disjoint Set) data structure is highly effective for detecting cycles in undirected graphs. It leverages the ability to efficiently determine if two nodes belong to the same connected component.
| Operation | Description | Time Complexity |
|---|---|---|
| Find | Determines the root of a node's set | O(log n) |
| Union | Merges two sets if they are disjoint | O(log n) |
Example: Cycle Detection in Graph
class UnionFind {
constructor(size) {
this.parent = Array.from({length: size}, (_, i) => i);
this.rank = new Array(size).fill(0);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // Path compression
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
if (this.rank[rootX] < this.rank[rootY]) {
[rootX, rootY] = [rootY, rootX];
}
this.parent[rootY] = rootX;
if (this.rank[rootX] === this.rank[rootY]) {
this.rank[rootX]++;
}
return true;
}
return false; // Cycle detected
}
}
function hasCycle(edges, n) {
const uf = new UnionFind(n);
for (const [u, v] of edges) {
if (!uf.union(u, v)) {
return true; // Cycle found
}
}
return false;
}
// Example usage:
const edges = [[0, 1], [1, 2], [2, 3], [3, 0]];
console.log(hasCycle(edges, 4)); // trueAlgorithm Summary
- Iterate through each edge in the graph.
- For each edge (u, v), check if u and v belong to the same set using
find. - If they do, a cycle is detected.
- If not, perform
unionto merge the sets.
5. Finding Number of Connected Components
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| find(x) | Find root of element x with path compression | O(α(n)) amortized | O(1) |
| union(x, y) | Merge components containing x and y | O(α(n)) amortized | O(1) |
| countComponents() | Count number of distinct components | O(1) | O(1) |
Example: Counting Connected Components in Graph
class UnionFind {
constructor(n) {
this.parent = Array.from({length: n}, (_, i) => i);
this.size = Array(n).fill(1);
this.components = n;
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // Path compression
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
if (this.size[rootX] < this.size[rootY]) {
[rootX, rootY] = [rootY, rootX];
}
this.parent[rootY] = rootX;
this.size[rootX] += this.size[rootY];
this.components--;
}
}
getComponentCount() {
return this.components;
}
}
// Example usage:
const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(2, 3);
console.log(uf.getComponentCount()); // Output: 3
Note: The
countComponents() method returns the number of distinct connected components in the Union-Find structure. It is updated during each union() operation.
6. Solving Redundant Connection
The Union-Find (Disjoint Set Union) data structure is particularly effective for solving the "Redundant Connection" problem, which involves identifying the redundant edge in a graph that forms a cycle when added to a tree.
| Property | Description | Usage |
|---|---|---|
| find(x) | Find the root of element x with path compression | Used to determine if two elements belong to the same set |
| union(x, y) | Merge the sets containing x and y | Used to connect two elements in the graph |
Example: Detecting Redundant Edge
function findRedundantConnection(edges) {
const parent = Array(1001).fill(0).map((_, i) => i);
const rank = Array(1001).fill(0);
function find(x) {
if (parent[x] !== x) {
parent[x] = find(parent[x]); // Path compression
}
return parent[x];
}
function union(x, y) {
const rootX = find(x);
const rootY = find(y);
if (rootX !== rootY) {
if (rank[rootX] < rank[rootY]) {
[rootX, rootY] = [rootY, rootX];
}
parent[rootY] = rootX;
if (rank[rootX] === rank[rootY]) {
rank[rootX]++;
}
return true;
}
return false; // Cycle detected
}
for (const [u, v] of edges) {
if (!union(u, v)) {
return [u, v];
}
}
}
Note: This solution uses path compression and union by rank for optimal performance, ensuring near-constant time operations.
7. Implementing Accounts Merge
| Property | Description | Example |
|---|---|---|
| unionFind | Union-Find data structure to group accounts | const uf = new UnionFind(accounts.length); |
| emailToIndex | Map from email to account index | const emailToIndex = new Map(); |
Example: Merging Accounts
class UnionFind {
constructor(size) {
this.parent = Array.from({length: size}, (_, i) => i);
this.rank = Array(size).fill(0);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
if (this.rank[rootX] < this.rank[rootY]) {
[rootX, rootY] = [rootY, rootX];
}
this.parent[rootY] = rootX;
if (this.rank[rootX] === this.rank[rootY]) {
this.rank[rootX]++;
}
}
}
}
function accountsMerge(accounts) {
const uf = new UnionFind(accounts.length);
const emailToIndex = new Map();
for (let i = 0; i < accounts.length; i++) {
const [name, ...emails] = accounts[i];
for (const email of emails) {
if (emailToIndex.has(email)) {
uf.union(i, emailToIndex.get(email));
} else {
emailToIndex.set(email, i);
}
}
}
const mergedAccounts = new Map();
for (let i = 0; i < accounts.length; i++) {
const root = uf.find(i);
if (!mergedAccounts.has(root)) {
mergedAccounts.set(root, []);
}
const account = mergedAccounts.get(root);
if (account.length === 0) {
account.push(accounts[i][0]);
}
for (let j = 1; j < accounts[i].length; j++) {
account.push(accounts[i][j]);
}
}
return Array.from(mergedAccounts.values());
}
8. Finding Sentence Similarity II
Given two sentences and a list of similar word pairs, determine if the sentences are similar. Similarity is transitive — if A is similar to B and B is similar to C, then A is similar to C.
| Property | Description |
|---|---|
| UnionFind | Used to group similar words into connected components. |
| Transitivity | Similarity is transitive, so Union-Find helps maintain connected components. |
Example: Sentence Similarity II
class UnionFind {
constructor() {
this.parent = new Map();
this.rank = new Map();
}
find(x) {
if (!this.parent.has(x)) {
this.parent.set(x, x);
this.rank.set(x, 0);
}
if (this.parent.get(x) !== x) {
this.parent.set(x, this.find(this.parent.get(x)));
}
return this.parent.get(x);
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
const rankX = this.rank.get(rootX);
const rankY = this.rank.get(rootY);
if (rankX < rankY) {
this.parent.set(rootX, rootY);
} else if (rankX > rankY) {
this.parent.set(rootY, rootX);
} else {
this.parent.set(rootY, rootX);
this.rank.set(rootX, rankX + 1);
}
}
}
}
function areSentencesSimilarTwo(sentence1, sentence2, similarPairs) {
if (sentence1.length !== sentence2.length) return false;
const uf = new UnionFind();
for (const [word1, word2] of similarPairs) {
uf.union(word1, word2);
}
for (let i = 0; i < sentence1.length; i++) {
const w1 = sentence1[i];
const w2 = sentence2[i];
if (w1 !== w2 && uf.find(w1) !== uf.find(w2)) {
return false;
}
}
return true;
}
// Example usage:
const sentence1 = ["I", "love", "leetcode"];
const sentence2 = ["I", "love", "onepiece"];
const similarPairs = [["love", "like"], ["like", "leetcode"]];
console.log(areSentencesSimilarTwo(sentence1, sentence2, similarPairs)); // true
Note: The Union-Find data structure is efficient for grouping similar words and checking if two words belong to the same group.
9. Solving Satisfiability of Equality
The Union-Find (Disjoint Set Union) data structure can be effectively used to solve satisfiability problems involving equality constraints. This approach is particularly useful when dealing with a set of equations that involve variables and equality relationships.
For example, given a list of equations like a == b, b == c, and a != c, we can determine whether the system of equations is satisfiable using Union-Find.
Example: Solving Equality Equations
class UnionFind {
constructor(n) {
this.parent = Array.from({length: n}, (_, i) => i);
this.rank = new Array(n).fill(0);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // Path compression
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
if (this.rank[rootX] < this.rank[rootY]) {
[rootX, rootY] = [rootY, rootX];
}
this.parent[rootY] = rootX;
if (this.rank[rootX] === this.rank[rootY]) {
this.rank[rootX]++;
}
}
}
isConnected(x, y) {
return this.find(x) === this.find(y);
}
}
function equationsPossible(equations) {
const uf = new UnionFind(26); // For 26 lowercase letters
// Process all equality equations first
for (const eq of equations) {
if (eq[1] === '=') {
const x = eq[0].charCodeAt(0) - 'a'.charCodeAt(0);
const y = eq[3].charCodeAt(0) - 'a'.charCodeAt(0);
uf.union(x, y);
}
}
// Check inequality equations
for (const eq of equations) {
if (eq[1] === '!') {
const x = eq[0].charCodeAt(0) - 'a'.charCodeAt(0);
const y = eq[3].charCodeAt(0) - 'a'.charCodeAt(0);
if (uf.isConnected(x, y)) {
return false;
}
}
}
return true;
}
// Example usage:
const equations = ['a==b', 'b!=c', 'c==a'];
console.log(equationsPossible(equations)); // false| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| find(x) | Finds the root of element x with path compression |
O(α(n)) amortized | O(n) |
| union(x, y) | Merges the sets containing x and y |
O(α(n)) amortized | O(n) |
| isConnected(x, y) | Checks if x and y are in the same set |
O(α(n)) amortized | O(n) |
Note: The inverse Ackermann function α(n) grows extremely slowly, making Union-Find operations nearly constant time in practice.
10. Finding Smallest String with Swaps
The Union-Find (Disjoint Set Union) data structure is useful for grouping indices that can be swapped based on a set of allowed swaps. By using Union-Find, we can efficiently group indices that are connected through a series of allowed swaps and then sort characters within each group to form the lexicographically smallest string.
| Property | Description | Example |
|---|---|---|
| Union-Find | Used to group indices that can be swapped. | parent[i] = i |
| Grouping | Each connected component in the Union-Find represents a group of indices that can be rearranged freely. | find(x) returns root of group |
| Sorting | Characters in each group are sorted to form the smallest string. | chars.sort() |
Example: Finding Smallest String with Swaps
function smallestStringWithSwaps(s, pairs) {
const n = s.length;
const parent = Array(n).fill(0).map((_, i) => i);
const rank = Array(n).fill(0);
function find(x) {
if (parent[x] !== x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
function union(x, y) {
const rootX = find(x);
const rootY = find(y);
if (rootX !== rootY) {
if (rank[rootX] < rank[rootY]) {
[rootX, rootY] = [rootY, rootX];
}
parent[rootY] = rootX;
if (rank[rootX] === rank[rootY]) {
rank[rootX]++;
}
}
}
for (const [a, b] of pairs) {
union(a, b);
}
const groups = new Map();
for (let i = 0; i < n; i++) {
const root = find(i);
if (!groups.has(root)) {
groups.set(root, []);
}
groups.get(root).push(i);
}
const result = Array(n);
for (const indices of groups.values()) {
const chars = indices.map(i => s[i]).sort();
indices.forEach((i, j) => result[i] = chars[j]);
}
return result.join('');
}
// Example usage:
const s = "dcab";
const pairs = [[0,3],[1,2]];
console.log(smallestStringWithSwaps(s, pairs)); // Output: "bacd"
Note: The Union-Find structure ensures that all indices in a connected component can be rearranged freely, allowing us to sort characters within each group to achieve the lexicographically smallest string.
11. Solving Number of Provinces
The Union-Find (Disjoint Set Union) data structure is particularly useful for solving the "Number of Provinces" problem, which involves identifying connected components in a graph.
| Property | Description | Usage |
|---|---|---|
| find | Find the root of a node with path compression | root = find(x) |
| union | Merge two sets if they are not already connected | union(x, y) |
| count | Number of disjoint sets (provinces) | count = unionFind.count |
Example: Number of Provinces
class UnionFind {
constructor(n) {
this.parent = Array.from({length: n}, (_, i) => i);
this.rank = new Array(n).fill(0);
this.count = n;
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // Path compression
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
if (this.rank[rootX] < this.rank[rootY]) {
[rootX, rootY] = [rootY, rootX];
}
this.parent[rootY] = rootX;
if (this.rank[rootX] === this.rank[rootY]) {
this.rank[rootX]++;
}
this.count--;
}
}
}
function findProvinces(isConnected) {
const n = isConnected.length;
const uf = new UnionFind(n);
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (isConnected[i][j] === 1) {
uf.union(i, j);
}
}
}
return uf.count;
}
// Example usage:
const isConnected = [
[1, 1, 0],
[1, 1, 0],
[0, 0, 1]
];
console.log(findProvinces(isConnected)); // Output: 2
Note: The Union-Find approach ensures efficient union and find operations with near-constant time complexity, making it ideal for large graphs.
12. Implementing Kruskal's MST
Example: Kruskal’s MST with Union-Find
class UnionFind {
constructor(size) {
this.parent = Array.from({length: size}, (_, i) => i);
this.rank = new Array(size).fill(0);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
if (this.rank[rootX] < this.rank[rootY]) {
[rootX, rootY] = [rootY, rootX];
}
this.parent[rootY] = rootX;
if (this.rank[rootX] === this.rank[rootY]) {
this.rank[rootX]++;
}
return true;
}
return false;
}
}
function kruskalMST(edges, vertices) {
edges.sort((a, b) => a.weight - b.weight);
const uf = new UnionFind(vertices);
const mst = [];
for (const edge of edges) {
if (uf.union(edge.from, edge.to)) {
mst.push(edge);
}
}
return mst;
}
// Example usage:
const edges = [
{from: 0, to: 1, weight: 4},
{from: 1, to: 2, weight: 8},
{from: 2, to: 3, weight: 7},
{from: 0, to: 3, weight: 6}
];
const mst = kruskalMST(edges, 4);
console.log(mst); // [{from: 0, to: 1, weight: 4}, {from: 1, to: 2, weight: 8}, {from: 0, to: 3, weight: 6}]
| Component | Description | Time Complexity |
|---|---|---|
| Union-Find Structure | Tracks connected components in a graph | O(α(n)) amortized |
| Edge Sorting | Sorts edges by weight in ascending order | O(E log E) |
| MST Construction | Processes sorted edges to build MST | O(E α(n)) |
Note: Union-Find with path compression and union by rank ensures near-constant time operations for large graphs.