Union-Find (Disjoint Set)

1The mental model (what this really is)#

Picture a room full of people. Some of them already know each other. You want to answer two kinds of questions fast:

• "Are these two people in the same friend group?"
• "These two just became friends, so merge their groups."

That is Union-Find. Nothing more. You keep a bunch of elements split into groups that never overlap (the "disjoint set" part), and you support two operations:

• find(x): which group does x belong to? Return a label for that group.
• union(a, b): merge the group of a with the group of b.

The clever bit is how you store it.

• Instead of keeping explicit member lists, each element just points at a "parent."
• Follow the parent pointers upward and you reach a root.
• The root is the group's identity.
• Two elements are in the same group if and only if they climb up to the same root.

So the whole structure is a forest of upward-pointing trees.

• find walks to the root.
• union makes one root point to the other.
• That is the entire idea, and it is one of the most elegant things in this corner of the field.

2How to recognize it (the signals in a problem)#

These are the tells I look for. If two or three fire, I reach for Union-Find before I finish reading the prompt.

• Connected components language: groups, clusters, provinces, islands, friend circles, or "is there a path between A and B."
• Edges arrive over time and you keep answering connectivity questions as they come. Union-Find loves an online stream of merges, exactly where it beats a one-shot DFS.
• Cycle detection in an undirected graph. Try to union two nodes that already share a root and that edge closes a cycle. The cleanest cycle test you will write.
• Grouping by equivalence: emails belonging to the same person, variables that must be equal, accounts to merge.
• A grid where you count regions but want something cleaner than repeated flood fill, or the merges arrive incrementally.
• "Minimum spanning tree." Kruskal's algorithm is Union-Find underneath, unioning edges in sorted order.

3The template (how it works, with pseudocode)#

Memorize this shape. It is maybe fifteen lines and it wins rounds. I write it from muscle memory so I can spend my thinking time on the problem, not the plumbing.

parent = [0, 1, 2, ..., n-1]  # each node starts as its own root
rank   = [0, 0, ..., 0]       # tree height hint, used for merging smartly

def find(x):
    # path compression: point everything directly at the root
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False  # already connected (useful for cycle detection)
    # union by rank: attach the shorter tree under the taller one
    if rank[ra] < rank[rb]:
        ra, rb = rb, ra
    parent[rb] = ra
    if rank[ra] == rank[rb]:
        rank[ra] += 1
    return True

Two optimizations matter, and you include both:

1. Path compression (inside find): after you find the root, flatten the path so next time the lookup is basically instant.

2. Union by rank (or by size): always hang the smaller tree under the bigger one so trees stay shallow.

3. Together they make each operation run in near-constant amortized time, O(alpha(n)), unpacked in section 6.

4. Interviewers want to hear you name both and say why, so do not just write them, narrate them.

A size-based variant is just as good and often more useful, because size[root] directly tells you how big a component is:

size = [1, 1, ..., 1]

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb: return False
    if size[ra] < size[rb]: ra, rb = rb, ra
    parent[rb] = ra
    size[ra] += size[rb]
    return True

• Pick size when the problem asks about the largest group or component counts (Making a Large Island is the poster child).
• Pick rank when it does not.
• Either is fine and both hit the same O(alpha(n)) bound.

4A worked example (walk through one problem step by step)#

Let me take a classic: count the number of provinces (LeetCode 547, also known as Friend Circles). You are given an n x n matrix where M[i][j] = 1 means city i and city j are directly connected. A province is a group of cities connected directly or indirectly. How many provinces are there?

First, recognize the shape. "Group of cities connected directly or indirectly" is a flashing neon sign for connected components. Union-Find fits.

The plan:

• Start with every city as its own province, so the count is n.
• Every time we union two cities that were in different provinces, the count drops by one.
• At the end, the count is the answer.

Say n = 4 and the connections are:

• city 0 and city 1 are connected
• city 1 and city 2 are connected
• city 3 is alone

Walk it through.

• Start. parent = [0,1,2,3]. Four separate roots. count = 4.
• Process M[0][1] = 1. union(0, 1). find(0) is 0, find(1) is 1. Different roots, so merge. Attach 1 under 0. parent becomes [0,0,2,3]. count drops to 3.
• Process M[1][2] = 1. union(1, 2). find(1) climbs: parent[1] is 0, so root is 0. find(2) is 2. Different roots, merge. parent becomes [0,0,0,3]. count drops to 2.
• City 3. Nobody connects to it. It stays its own root.
• Answer: 2 provinces. One is {0, 1, 2}, the other is {3}.

Notice two things:

• I never built an explicit list of who is in each group. The parent array carried all of it.
• I let union tell me whether a real merge happened by checking if the roots differed, which is how I keep the running count honest.
• I only scan the upper triangle of the matrix (j > i) since it is symmetric, so no pair gets processed twice.

In code the core loop is tiny:

count = n
for i in range(n):
    for j in range(i+1, n):
        if M[i][j] == 1 and union(i, j):
            count -= 1
return count

• That is the whole thing. The structure does the heavy lifting.
• Reading the matrix dominates the cost at O(n^2), and the Union-Find work on top of it is effectively free.

5Variations and gotchas#

The interviewer rarely hands you clean integers and a ready matrix. Here is the twist they bolt on, and how you absorb it.

• Mapping non-integer elements. Nodes are often strings, coordinates, or emails, not clean 0-to-n integers. Keep a dictionary that maps each item to an integer index the first time you see it, then run normal Union-Find on the indices. Do not hash strings into the parent array directly. Accounts Merge is the canonical case.
• 2D grids flattened to 1D. For an r x c grid, index cell (i, j) as i * c + j. Then union each land cell with its right and down neighbors only, so you cover every edge exactly once. This handles counting islands or the "number of islands II" streaming variant.
• Weighted, with offsets. Some problems track a relationship, not just membership: "a is 3 units heavier than b," currency exchange rates, or "satisfiability of equality equations." Store a weight on each parent pointer and keep it consistent during path compression. This is the advanced flavor and a strong signal you are in a senior interview. Evaluate Division is the one they reach for.
• Counting components live. Keep a count variable, start it at n, decrement on every successful union. Do not recompute by scanning for distinct roots each time, that is slow and sloppy.
• Bipartite, two-color problems. Model "these two must be enemies" by giving each element a virtual twin and unioning across camps. A neat pattern for "possible bipartition" style questions.

6Complexity#

With both path compression and union by rank or size, each find and union runs in O(alpha(n)) amortized, where alpha is the inverse Ackermann function.

• In plain terms, alpha(n) is less than 5 for any input you will ever see, even inputs the size of the number of atoms in the universe.
• So treat it as effectively constant and say so.
• Building the structure over m operations: O(m * alpha(n)), which is basically O(m).
• Space: O(n) for the parent array, plus O(n) for rank or size.

Drop both optimizations and a single find can degrade to O(n) because the tree becomes a straight line.

• That turns a fast solution into an O(n^2) disaster on adversarial input.
• Interviewers know this and will feed you the worst case. Keep both optimizations in.

Against BFS or DFS for a one-shot component count, Union-Find is similar in time but shines when merges arrive incrementally or you answer many connectivity queries interleaved with updates. That online quality is its edge, and the reason to pick it over a flood fill when both would pass.

7Mistakes that cost people the round#

• Forgetting path compression, union by rank, or both. The single most common miss. Your code is "correct" but slow, and the interviewer watches you fail the big test case. Put both in from the start.
• Comparing elements instead of roots in union. You must union the roots, find(a) and find(b), not a and b directly. Attaching a non-root silently corrupts the forest, and the bug is painful to spot later.
• Recursion depth. Recursive find can blow the stack on a long chain in languages with shallow limits (Python defaults to about 1000 frames). If n is large, write find iteratively or guarantee compression kicks in early.
• Rebuilding or recounting components the slow way. Scanning all nodes for distinct roots after every union is the trap that turns O(alpha) into O(n). Maintain a counter.
• Off-by-one and index mapping bugs when flattening a grid or mapping strings. Double check i * c + j, and make sure every element gets a stable index.
• Reaching for Union-Find when edges get deleted. It cannot un-merge. If you hear "remove an edge," rethink. Processing queries in reverse can turn deletions into additions, the clever save, but that is a deliberate design choice, not the default.

8Your practice path (named problems by difficulty)#

Do them in this order. Each one adds a new wrinkle, so resist jumping ahead.

Warm up (get the template in your fingers):

• Number of Provinces (a.k.a. Friend Circles), LeetCode 547
• Number of Connected Components in an Undirected Graph, LeetCode 323
• Find if Path Exists in Graph, LeetCode 1971

Build the core patterns:

• Number of Islands (do it with Union-Find even though DFS works, to practice grid flattening), LeetCode 200
• Graph Valid Tree (cycle detection plus edge count check), LeetCode 261
• Redundant Connection (the cleanest cycle-detection-via-union problem there is), LeetCode 684
• Accounts Merge (string-to-index mapping, grouping by root), LeetCode 721

Level up:

• Most Stones Removed with Same Row or Column, LeetCode 947
• Satisfiability of Equality Equations, LeetCode 990
• Number of Islands II (online, streaming merges, where Union-Find clearly beats flood fill), LeetCode 305
• Smallest String With Swaps, LeetCode 1202

Senior / weighted and advanced:

• Evaluate Division (weighted Union-Find with ratios), LeetCode 399
• Possible Bipartition (virtual-twin trick), LeetCode 886
• Making a Large Island, LeetCode 827
• Swim in Rising Water (Union-Find plus a sweep), LeetCode 778

If you can do Redundant Connection and Accounts Merge cold, and explain Evaluate Division's weighting, you are in good shape for any Union-Find question a loop throws at you.

9Where this shows up#

• Union-Find is a favorite at companies that care about graph fundamentals over trivia.
• Google and Meta use it for connectivity and grouping rounds.
• Amazon leans on the grid and island variants.
• It appears in system-flavored questions about merging accounts, deduping entities, or clustering, where the interviewer wants to see you pick the right structure, not just brute force it.
• Kruskal's MST shows up in the occasional harder round, and Union-Find is the heart of it.

Learn it once, really learn it, and it pays off across a surprising range of problems.

Want to see which companies lean hardest on this pattern and in which rounds? Check the company guides to map it to your target.