Union Find / Disjoint Set Pattern: Coding Interview Guide

When To Use the Union Find Pattern

Pattern recognition is the meta-skill in coding interviews. Union Find is the right tool in the following situations, and learning to spot them in under 30 seconds is how strong candidates avoid the brute-force trap.

• Number of connected components in an undirected graph
• Detect redundant connection (cycle in undirected)
• Kruskal's minimum spanning tree
• Accounts merge (group emails by user)
• Friend circles / island problems (alternative to BFS)

If you see two or more of these signals in the problem statement, default to union find as your first approach. If the brute-force pass doesn't fit, this is usually the next stop.

Template Code

Memorize this skeleton. In real interviews you should be able to type it from muscle memory in under two minutes, then specialize the inner logic for the specific problem. The bug surface in union find is usually in the inner conditional, not the outer loop, so getting the boilerplate right protects you from off-by-one mistakes.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path compression
            x = self.parent[x]
        return x
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        if self.rank[px] < self.rank[py]: px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]: self.rank[px] += 1
        return True

This template is the Python form. The same shape translates directly to Java, C++, Go, and JavaScript; only the container types change. Practicing the template in your strongest language first builds the right mental model before you port it.

Time and Space Complexity

• Time: Near O(1) amortized per op with path compression + union by rank
• Space: O(n) parent + rank arrays

State the complexity out loud at the start of every problem you solve with this pattern. Interviewers grade on whether you reason about complexity before writing code, not after.

Classic Problems To Practice

Drill these in order. The first 2-3 establish the template, the middle ones add a twist (duplicates, multiple constraints, edge cases), and the last ones combine union find with a second pattern. Working all of them is roughly 8-12 hours of focused practice.

• Number of Connected Components
• Redundant Connection
• Accounts Merge
• Number of Islands II
• Most Stones Removed With Same Row or Column
• Satisfiability of Equality Equations
• Swim in Rising Water

After finishing the list, do a timed mock with one problem from this pattern picked at random. If you can solve it in under 25 minutes with no hints and a clean complexity analysis, you have internalized the pattern.

Companies That Ask the Union Find Pattern

Based on LeakCode's aggregated interview reports, union find questions appear regularly in coding rounds at the following companies. Click any to see their full question pool.

Patterns are not company-specific in theory but in practice some companies lean harder than others. Meta and Amazon are known for two-pointer and sliding-window heavy phone screens; Google leans graph and DP; Stripe favors design-leaning patterns. Calibrate your prep mix by checking the recent reports for your target company before drilling generic lists.

Common Mistakes

These are the failure modes that show up most in LeakCode reports from candidates who got "no hire" or "weak hire" on rounds where this pattern was expected.

• Forgetting path compression (turns O(α(n)) into O(n) per op)
• Using union without rank/size heuristic
• Treating directed edges as undirected
• Counting components after partial union calls

Read each mistake, then write the template again from scratch making sure you handle the corresponding edge case. The mistakes are easier to internalize when you have made them once in a low-stakes context than when you discover them in a real interview.

How To Practice This Pattern

The fastest way to internalize union find is deliberate practice with constraint, not raw volume. Three sessions of 90 minutes each beat one session of 6 hours because spaced practice consolidates the pattern recognition wiring.

Session 1: read the template, draw the state diagram on paper, then solve the first 3 classic problems with the template visible. Goal is template fluency, not problem solving.

Session 2: solve problems 4-7 without looking at the template. If you blank, look, then close and restart from scratch. Goal is unaided recall of the template under no time pressure.

Session 3: timed mock with the remaining problems on a 25-minute clock each. Talk through complexity out loud as you would in an interview. Goal is performance under interview tempo. After this session, the pattern should feel obvious when you see a matching problem.