Union Find: Code Templates in 6 Languages
If you have not read the concept guide yet, start there for the intuition and the complexity analysis. This page has the code you can reproduce from memory in an interview: a standard Union Find with path compression and union by rank, plus union by size for component questions and Kruskal’s algorithm for minimum spanning trees.
Main Template: Union Find with Union by Rank
This is the default version of the pattern. It handles connectivity checks, component counting, and cycle detection in undirected graphs. Every operation runs in amortized
Use this for Find if Path Exists in Graph and Number of Provinces on the practice problems page.
class UnionFind {
constructor(size) {
this.parent = new Array(size);
this.rank = new Array(size).fill(0);
for (let i = 0; i < size; i++) {
this.parent[i] = i;
}
}
find(x) {
// Walk up to the root, then rewire every node on the
// path to point straight at it so later finds are cheap
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) return false; // same group already
// Attach the shorter tree under the taller one.
// Equal ranks: pick either side and grow it by one.
if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
return true;
}
connected(x, y) {
return this.find(x) === this.find(y);
}
}Code Breakdown
Key Variables
parent: the tree itself, flattened into an array.parent[i]is the parent of element i, and the root of a group is the element whose parent is itself.rank: a rough measure of tree height, used only during union. The rank of the root grows when two trees of equal rank merge.
Visual Mechanism
The find operation is where the structure pays for itself. Every call flattens the path it walks, so the second find on the same elements is shorter than the first.
graph TD
A["find(x)"] --> B{"parent[x] == x?"}
B -->|"Yes"| R["x is the root. Return x"]
B -->|"No"| C["parent[x] = find(parent[x])"]
C --> R
R --> D["Path compressed: nodes on the route point at the root"]
Critical Sections
The initialization sets every element as its own root. Elements that never appear in a union stay that way, which is correct: an element on its own is a group of one.
The find recursion is the whole point of the data structure. It resolves the root, and the assignment on the way back rewires each node it visited to point straight at the root. Without that assignment, the structure still works, but repeated finds on the same path stay expensive.
The union logic decides which tree becomes the child. Rank keeps the trees balanced, and the recursion in find stays shallow because of it. That is the detail to mention when an interviewer asks why the operations are near-constant.
Variations
1. Union by Size (Component Sizes)
Some problems need the size of a component, like the largest island after a flip. Track the number of elements in each tree instead of its rank, and attach the smaller component under the larger one. The balance guarantee is the same, and the size information comes for free.
Use this for Making A Large Island on the practice problems page.
Visual
graph TD
A["Component A: size 2"] --> C["Merged root, size 5"]
B["Component B: size 3"] --> C
class UnionFindSize {
constructor(size) {
this.parent = new Array(size);
this.size = new Array(size).fill(1);
for (let i = 0; i < size; i++) {
this.parent[i] = i;
}
}
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) return false;
// Attach the smaller component under the larger one
// and fold the sizes together
if (this.size[rootX] < this.size[rootY]) {
this.parent[rootX] = rootY;
this.size[rootY] += this.size[rootX];
} else {
this.parent[rootY] = rootX;
this.size[rootX] += this.size[rootY];
}
return true;
}
getSize(x) {
return this.size[this.find(x)];
}
}2. Kruskal’s Minimum Spanning Tree
Kruskal’s algorithm builds a minimum spanning tree by sorting edges by cost and accepting each edge whose endpoints are not already connected. Union Find supplies the connectivity check, which is the expensive part of a naive solution. The sort costs
Use this for Min Cost to Connect All Points on the practice problems page.
Visual
graph TD
S["Sort edges by cost"] --> T["Take cheapest remaining edge"]
T --> C{"Endpoints already connected?"}
C -->|"Yes"| D["Skip: would close a cycle"]
C -->|"No"| A["Accept, add cost, union endpoints"]
D --> T
A --> T
function kruskalMST(n, edges) {
// edges: [cost, u, v]. Sorting cheapest first means every
// accepted edge is the cheapest one that cannot close a cycle.
edges.sort((a, b) => a[0] - b[0]);
const parent = Array.from({ length: n }, (_, i) => i);
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
let total = 0;
let used = 0;
for (const [cost, u, v] of edges) {
const rootU = find(u);
const rootV = find(v);
if (rootU !== rootV) {
parent[rootU] = rootV;
total += cost;
if (++used === n - 1) break; // spanning tree is complete
}
}
return total;
}One note on the recursive find. Union by rank keeps tree depth logarithmic, so the recursion depth stays small even for large inputs. An iterative find only matters for adversarial inputs in competitive programming. You will not need it in an interview.
Now head to the practice problems to apply these templates to real interview questions.