Union-Find Pattern for Coding Interviews: 2026 Guide

The Union-Find pattern, also known as Disjoint Set Union (DSU), is one of the most efficient data structures for solving connectivity and grouping problems in coding interviews. Whether you are preparing for FAANG interviews or competitive programming contests in 2026, mastering Union-Find gives you a powerful tool for problems involving connected components, cycle detection, and dynamic equivalence relations. In this guide, we cover everything you need to know: how it works, when to use it, optimized implementation in Java, the most commonly asked interview problems, and a structured practice plan.

What Is Union-Find (Disjoint Set Union)?

Union-Find is a data structure that tracks a collection of elements partitioned into non-overlapping (disjoint) sets. It supports two primary operations efficiently:

• Find(x): Determine which set element x belongs to by returning the root representative of that set.
• Union(x, y): Merge the sets containing elements x and y into a single set.

Think of it like a social network: each person belongs to a friend group. Find tells you which group someone is in, and Union merges two friend groups when two people from different groups become friends. The structure uses a parent array where each element points to its parent, and the root of each tree serves as the set identifier.

When Should You Use Union-Find?

Reach for Union-Find whenever you see these patterns in an interview problem:

• Grouping or connectivity: “Are these two nodes connected?” or “How many groups exist?”
• Dynamic edge additions: Edges are added over time, and you need to track connectivity after each addition.
• Cycle detection in undirected graphs: If a union operation tries to merge two nodes already in the same set, a cycle exists.
• Equivalence relations: Merging accounts, synonyms, equivalent equations, or similar grouping operations.

If BFS or DFS feels heavy for a connectivity problem, or the graph is built incrementally, Union-Find is almost certainly the cleaner solution.

Union by Rank and Path Compression

A naive Union-Find implementation can degrade to O(n) per operation if the tree becomes a long chain. Two critical optimizations bring it down to nearly O(1) amortized:

Path Compression

During a find operation, path compression flattens the tree by making every node on the path point directly to the root. This means future queries on those nodes are instant. It is implemented by setting parent[x] = find(parent[x]) recursively.

Union by Rank

When merging two sets, union by rank attaches the shorter tree under the root of the taller tree. This keeps trees shallow. The rank is an upper bound on the tree height and only increases when two trees of equal rank are merged.

Together, these two optimizations yield an amortized time complexity of O(α(n)) per operation, where α is the inverse Ackermann function — effectively constant for all practical input sizes.

Java Implementation Template

Here is a complete, interview-ready Java implementation with both optimizations:

class UnionFind {
    private int[] parent;
    private int[] rank;
    private int components;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        components = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return false; // Already connected

        // Union by rank
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        components--;
        return true;
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public int getComponents() {
        return components;
    }
}

This template handles 90% of Union-Find interview problems. The union method returns false if both elements are already connected, which is useful for cycle detection. The components counter tracks the number of disjoint sets, which many problems ask for directly.

Common Interview Problems Using Union-Find

These four problems appear frequently in technical interviews at top companies and cover the core applications of Union-Find:

1. Number of Connected Components (LeetCode 323)

Given n nodes and a list of edges, find how many connected components exist. Initialize a UnionFind with n nodes, union each edge, and return getComponents(). This is the purest application of the pattern.

2. Redundant Connection (LeetCode 684)

Find the edge that, if removed, makes the graph a tree. Process edges in order: the first edge where union(u, v) returns false means u and v are already connected, making this the redundant edge that creates a cycle.

3. Accounts Merge (LeetCode 721)

Given accounts where each has a name and email list, merge accounts sharing any email. Map each email to an index, union all emails within each account, then group emails by their root representative. This demonstrates Union-Find beyond simple graph edges — it handles equivalence grouping elegantly.

4. Earliest Moment When Everyone Becomes Friends (LeetCode 1101)

Given timestamped friendship events, find the earliest time when all people are connected. Sort events by timestamp, process each with union, and return the timestamp when components == 1. This tests your ability to combine sorting with Union-Find.

Worked Example: Redundant Connection

Let us walk through LeetCode 684 step by step. Given edges: [[1,2], [1,3], [2,3]] with n = 3.

Step 1: Initialize UnionFind with 3 nodes. Parent: [0, 1, 2], each node is its own root.

Step 2: Process edge [1,2]. Nodes 1 and 2 have different roots, so union them. Parent becomes [0, 1, 1]. Components: 2.

Step 3: Process edge [1,3]. Nodes 1 and 3 have different roots (1 and 3), so union them. Parent becomes [0, 1, 1] with node 3 pointing to 1. Components: 1.

Step 4: Process edge [2,3]. Find(2) = 1, Find(3) = 1. Same root! Union returns false. This is the redundant edge. Return [2, 3].

The key insight: when union returns false, both nodes already share a root, meaning adding this edge creates a cycle.

Complexity Analysis

With both path compression and union by rank:

• Time complexity: O(α(n)) per find/union operation, where α(n) is the inverse Ackermann function. For all practical values of n (up to 10⁸⁰), α(n) ≤ 4. This means each operation is effectively O(1).
• Space complexity: O(n) for the parent and rank arrays.
• For m operations on n elements: Total time is O(m · α(n)), which is nearly O(m).

Compared to BFS/DFS for connectivity queries, Union-Find is superior when edges are added dynamically or when you need repeated connectivity checks. BFS/DFS requires O(V + E) per query, while Union-Find answers in near-constant time after initial setup.

Two-Week Practice Plan

Days 1–3 (Foundation): Implement Union-Find from scratch without looking at references. Solve Number of Connected Components and Number of Provinces. Focus on getting the template into muscle memory.

Days 4–7 (Core problems): Tackle Redundant Connection, Accounts Merge, and Satisfiability of Equality Equations. Practice identifying when Union-Find applies versus BFS/DFS.

Days 8–11 (Advanced): Solve Earliest Moment When Everyone Becomes Friends, Most Stones Removed, and Smallest String With Swaps. These require combining Union-Find with sorting or additional data structures.

Days 12–14 (Mock interviews): Do timed practice. Given a new problem, you should recognize the Union-Find pattern and write the solution within 20 minutes. Review any problems where you struggled.

Level Up Your Interview Prep with Niraswa AI

Mastering Union-Find is just one piece of the puzzle. At Niraswa AI, we help software engineers navigate every stage of their career journey — from cracking coding interviews to negotiating top offers. Our AI-powered platform provides personalized practice, real-time feedback, and expert-curated problem sets designed for 2026 interview trends. Whether you are targeting FAANG, startups, or remote-first companies, Niraswa AI equips you with the tools and strategies to land your dream role. Start your preparation today and turn patterns like Union-Find into second nature.