Union-Find Interview Pattern: When to Use It and 5 Problems to Practice (2026)

When you see a question that talks about connected components, friend circles, clusters, or merging groups, the union‑find (also called Disjoint Set Union, DSU) pattern is often the right tool. It lets you maintain a collection of disjoint sets and merge them quickly while being able to ask "are these two elements in the same set?". The whole idea is simple: each element points to a "parent"; the root of a tree is its own parent. Two operations are needed:

• Find – follow parent pointers until you reach the root. With path compression, you flatten the tree on the way back, making future finds faster.
• Union – attach the root of one tree to the root of another. Using union by rank (or size) keeps the trees shallow.

Together they give almost‑O(1) amortized time, which is fast enough for the typical interview constraints (hundreds of thousands of elements, tens of thousands of operations).

Recognizing the Union‑Find Signal

If the problem asks you to process many pairwise relationships and then answer queries about membership, you are likely looking at a union‑find solution.

A Worked Example in Python

Below is a concise, interview‑ready implementation. It includes both path compression and union by rank.

class DSU:
    def __init__(self, n: int):
        # parent[i] = i initially, rank[i] = 0
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # optional: number of disjoint sets

    def find(self, x: int) -> int:
        # iterative version with path compression
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]  # halve the path
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False  # already in the same set
        # union by rank
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.count -= 1
        return True

Sample Problem: Number of Islands

Given a 2‑D grid of 1s (land) and 0s (water), count the number of islands. An island is a group of adjacent lands (horizontal/vertical).

Idea: Treat each cell as a node. When you see a 1, union it with any neighboring 1s. After processing the whole grid, the number of distinct roots equals the number of islands.

def num_islands(grid):
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    dsu = DSU(rows * cols)
    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    def idx(r, c):
        return r * cols + c
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '0':
                dsu.count -= 1  # water cells are not islands
                continue
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                    dsu.union(idx(r, c), idx(nr, nc))
    return dsu.count

The solution runs in O(R·C·α(N)) time, where α is the inverse Ackermann function (practically constant), and O(R·C) space.

Common Pitfalls

1. Off‑by‑one indexing – Remember to map 2‑D coordinates to a 1‑D index correctly.
2. Counting water cells – If you start with n elements, you must subtract the ones that never become land.
3. Skipping union when both sides are already in the same set – This can cause an extra decrement of the set count.
4. Mixing up find return values – Always use the root returned by find; comparing the original elements directly is a bug.
5. Not resetting the DSU between test cases – In a multi‑test scenario, re‑initializing the structure avoids cross‑contamination.

Five Representative Practice Problems

1. Friend Circles (LeetCode 547 style)

Prompt: Given an N×N matrix M where M[i][j] = 1 means person i and j are direct friends, compute the number of friend circles. Hint: Union each pair (i, j) where M[i][j] == 1. The answer is the number of distinct roots.

2. Redundant Connection (LeetCode 684 style)

Prompt: An undirected graph with N nodes has exactly one extra edge that creates a cycle. Return that edge. Hint: Process edges in order; the first edge whose two endpoints already share a root is the redundant one.

3. Smallest String With Swaps (LeetCode 1202 style)

Prompt: You can swap characters at indices given by pairs. Find the lexicographically smallest string possible. Hint: Union all indices that can reach each other. For each component, sort the characters and place them back in order.

4. Minimum Cost to Connect All Points (Kruskal variant)

Prompt: Given points on a plane, connect them with edges of Manhattan distance. Return the minimum total cost. Hint: Generate all edges, sort by weight, then use DSU to add edges while avoiding cycles (Kruskal's algorithm).

5. Equations Possible (LeetCode 990 style)

Prompt: You have equations like a==b or a!=b. Determine if they can all be satisfied. Hint: First union all == pairs, then verify that no != pair shares a root.

Each of these problems stresses a different facet: counting components, detecting cycles, grouping indices, building a spanning tree, and reasoning about constraints. Solving them will make the union‑find pattern feel natural.

How to Practice This

1. Implement from scratch – Write the DSU class without looking at references. Run a quick sanity test (e.g., union a few numbers and check find).
2. Solve one problem per day – Pick one of the five practice problems, code it, and then manually trace the algorithm on a small example.
3. Explain aloud – Use Call Assistant to rehearse your explanation. Speaking the reasoning helps you keep the narrative clear during a real interview.

---

FAQ

• When is union‑find not the right choice? If the problem requires shortest‑path queries, dynamic edge deletions, or weighted unions, graph algorithms like BFS/DFS or Dijkstra are usually better.

• Do I need both path compression and union by rank? You can get acceptable performance with just one, but the combination gives the near‑constant amortized cost most interviewers expect.

• How many lines of code should I aim for? Keep the DSU implementation under 15 lines; the surrounding logic (reading input, building edges) should be concise but readable.

• Can I use recursion for find? Recursive find works, but an iterative version avoids recursion depth issues on large inputs and is often preferred in interviews.