Union-Find (Disjoint Set)

Question 1

What is the primary optimization that makes Union-Find nearly constant time?

Accepted Answer

Path compression — Path Compression flattens the tree structure during Find operations, ensuring future operations are very fast.

Question 2

A Union-Find (Disjoint Set Union) structure supports which two core operations?

Accepted Answer

find and union — find returns the representative (root) of an element's set; union merges two sets. Together they track a partition of elements into disjoint groups.

Question 3

With path compression AND union by rank/size, the amortized cost per operation is…

Accepted Answer

O(α(n)) amortized — effectively constant — Combining both optimizations gives O(α(n)) amortized, where α grows so slowly it's ≤ 4 for any practical n — effectively constant.

Question 4

PATH COMPRESSION optimizes find by…

Accepted Answer

By pointing visited nodes directly to the root — During find, every node on the path is re-pointed to the root, so future finds are nearly O(1).

Question 5

UNION BY RANK (or size) keeps trees shallow by…

Accepted Answer

By attaching the smaller tree under the larger one's root — Hanging the smaller tree beneath the larger root prevents tall degenerate chains, bounding tree height (logarithmic before compression, near-constant with it).

Question 6

Union-Find is the key data structure inside which MST algorithm?

Accepted Answer

Kruskal's — Kruskal's adds edges in increasing weight, using Union-Find to check whether an edge would form a cycle (endpoints already connected).

Question 7

Union-Find detects a cycle in an UNDIRECTED graph when…

Accepted Answer

An edge connects two nodes that already share a root — If find(u) == find(v) before adding edge (u,v), the two are already connected, so the edge would close a cycle.

Question 8

The 'representative' of a set in Union-Find is…

Accepted Answer

The root of its tree — Each set is a tree whose root (parent of itself) serves as the canonical identifier; two elements share a set iff they share a root.

Question 9

What problem is Union-Find especially suited for versus repeated BFS/DFS?

Accepted Answer

Dynamic connectivity with incremental union queries — Union-Find handles a stream of merge/connectivity queries in near-constant time each, whereas re-running BFS/DFS per query is O(V+E) each.

Question 10

What is the space complexity of Union-Find over n elements?

Accepted Answer

O(n) for the parent array — It stores a parent pointer (and a rank or size) per element — O(n).

Union-Find (Disjoint Set)

union(x, y)

Test your knowledge

What is the primary optimization that makes Union-Find nearly constant time?

Write the code

Number of Provinces

Example Cases

The short version

In more depth

Disjoint Sets

When to reach for this

Interview Questions

References & Further Reading

Love this visualization?