Intermediate 10 min read

Union-find (disjoint sets)

In one line

Union-find keeps track of which items belong to the same group and merges groups in nearly constant time, using a parent pointer per item, path compression and union by size.

What it is

Union-find, also called a disjoint set union (DSU), manages a collection of items split into non-overlapping groups. It supports two operations: find(x) returns a representative (the root) of x's group, and union(a, b) merges the groups of a and b. Two items are connected exactly when find returns the same root for both.

Each group is stored as a tree of parent pointers, and the root points to itself. Find follows parents up to the root. Union finds both roots and points one root at the other.

Two tricks make it fast. Union by size (or rank) attaches the smaller tree under the larger, keeping trees shallow. Path compression makes nodes visited during find point closer to (or directly at) the root. Together, each operation costs O(alpha(n)) amortized, where alpha is the inverse Ackermann function, which is at most 4 for any realistic n, so effectively constant.

Why interviewers ask

Number of provinces, redundant connection, accounts merge, number of islands II and Kruskal's minimum spanning tree are union-find problems. Interviewers want to see the two optimisations, a correct cycle check (union of already-connected nodes), and when union-find beats BFS or DFS, mainly when edges arrive over time.

How it works

1Initialise parent[i] = i and size[i] = 1 for every item: each item is its own group.
2find(x): while parent[x] != x, move up. With path compression, rewrite pointers along the way so future finds are shorter.
3union(a, b): compute ra = find(a) and rb = find(b). If they are equal, a and b are already connected; in an edge-by-edge build, this edge would create a cycle.
4Otherwise attach the root of the smaller tree under the root of the larger one and add the sizes. The number of groups drops by one.
5connected(a, b) is just find(a) == find(b).
6Union-find only merges. It cannot split a group apart; for deletions you need a different approach, such as processing operations in reverse.

Worked example · Five items, three unions

Start: parent = [0, 1, 2, 3, 4], size all 1, groups = 5.
union(0, 1): roots 0 and 1, equal sizes, attach 1 under 0. parent = [0, 0, 2, 3, 4], size[0] = 2, groups = 4.
union(2, 3): attach 3 under 2. parent = [0, 0, 2, 2, 4], size[2] = 2, groups = 3.
union(1, 3): find(1) = 0 and find(3) = 2. Sizes tie at 2, so attach 2 under 0. parent = [0, 0, 0, 2, 4], size[0] = 4, groups = 2.
find(3): 3 to 2 to 0. Path compression sets parent[3] = 0, so the next find(3) is one step.
connected(1, 2)? find(1) = 0 and find(2) = 0: yes. connected(0, 4)? 0 vs 4: no. union(1, 2) now returns False, meaning such an edge would close a cycle.

Picture it

Think of clubs where every member knows one contact who leads them toward the club president. To check if two people are in the same club, ask both chains for their president. When two clubs merge, the smaller club's president simply starts reporting to the larger club's president.

Reference code

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.groups = n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False              # already connected: this edge closes a cycle
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra          # attach the smaller tree under the larger
        self.size[ra] += self.size[rb]
        self.groups -= 1
        return True

find uses path halving (each node skips to its grandparent), a simple iterative form of path compression with the same guarantees. union by size keeps trees shallow and returns False when both items are already in one group. With both tricks, operations are O(alpha(n)) amortized.

Key patterns

Count connected components

When: Number of provinces, graph valid tree, number of operations to connect a network

How: Start with n groups and decrement on each successful union; a valid tree needs exactly n - 1 successful unions and no failed ones.

Cycle detection in undirected graphs

When: Redundant connection, Kruskal

How: Process edges in order; the first edge whose endpoints already share a root is the one that closes a cycle.

Kruskal's minimum spanning tree

When: Min cost to connect all points or cities

How: Sort edges by weight and union each edge that connects two different groups until n - 1 edges are added. O(E log E).

Group by shared keys

When: Accounts merge, similar strings, synonym groups

How: Map each key (email) to the first item that had it and union later items with it; then collect members by root.

Dynamic connectivity with additions

When: Number of islands II, online connectivity queries

How: Add cells or edges one at a time and answer connected or count queries after each, which BFS would recompute from scratch.

Real-world use

Network design with Kruskal's algorithm

Kruskal's minimum spanning tree sorts cable or road links by cost and adds each one unless union-find says its two ends are already connected, giving the cheapest network that reaches every site.

Image processing

Connected-component labelling in libraries such as OpenCV uses union-find in its classic two-pass algorithm to merge provisional labels of touching pixels, for example to count cells in a microscope image.

Identity resolution

Companies merging customer records union together accounts that share an email, phone number or device, so every group of linked records becomes one customer profile.

Compilers and type inference

Type checkers for languages like OCaml and Haskell use union-find to unify type variables: when two types must be equal, their sets are merged.

In a project

A fintech app must flag fraud rings: groups of accounts linked by a shared phone, device, card or address. About 5 million accounts and 20 million shared-attribute links arrive throughout the day.

Give each account an integer id and create a DSU with parent and size arrays.
For each attribute value (a device id, say), keep the first account that used it; when another account uses it, union the two.
Track group sizes in the root and alert when a group grows past a threshold, for example 20 accounts sharing devices.
Process links as a stream: each union is near O(1), so new links are handled in real time without recomputing the whole graph.
Nightly, rebuild from scratch to drop links that have expired, since union-find cannot split groups.

Impact: Fraud rings are detected as links arrive instead of in a slow nightly graph job, and 20 million unions take seconds of CPU, letting analysts review suspicious groups the same day.

Trade-offs

Use it when

Edges or links arrive over time and you need connectivity answers after each one
Counting or merging groups, detecting cycles in undirected graphs, Kruskal's MST
You need many connected(a, b) queries and only ever add connections

Avoid it when

You need to delete edges or split groups: union-find cannot undo merges
You need actual paths or distances between nodes: use BFS, DFS or Dijkstra
The graph is directed and you need reachability or cycles: union-find ignores direction

Cost: O(alpha(n)) amortized per find or union with path compression and union by size, effectively constant. O(n) space. Without either optimisation, a find can be O(n).

Common mistakes

Setting parent[a] = b directly instead of linking the roots, which breaks groups apart.
Comparing parent[a] == parent[b] instead of find(a) == find(b); parents are not necessarily roots.
Skipping both union by size and path compression, so trees degrade into chains and finds become O(n).
Using union-find for directed graph problems such as course schedule, where direction matters.
Saying operations are O(log n) or exactly O(1); the accurate bound with both optimisations is O(alpha(n)) amortized.

Interview questions

Quick revision

parent[i] = i at the start; the root represents the group.
find: follow parents to the root, compressing the path.
union: link root to root, smaller under larger.
union returns False when already connected: a cycle edge.
Both optimisations give O(alpha(n)) amortized, effectively O(1).
Track the group count: start at n, minus 1 per successful union.
Merges only; no splits. Undirected connectivity only.
Kruskal = sort edges + union-find.

Check yourself

1. After union(0, 1), union(2, 3) and union(1, 3) on 5 items, how many groups are there?

2. union(a, b) finds that find(a) == find(b). In Kruskal's algorithm or redundant connection, what does this mean?

3. What is the amortized cost per operation with both path compression and union by size?

4. Which problem is union-find NOT a good fit for?

Depth-first search Representing graphs When greedy works (exchange argument)Shortest paths (Dijkstra)

Saved on this device. Create a free account to keep it on every device.

Shortest paths (Dijkstra)

Practise this with Sam

A real mock interview, out loud, with an honest scorecard. Free to start.

Start free