Union-Find (Disjoint Set Union): Path Compression, Union by Rank & Interview Problems

Union-find is the data structure most candidates learn last and use least, which is exactly why it impresses interviewers. Many problems that look like they need repeated BFS or a clever graph construction collapse into a few union calls and a find. And unlike segment trees or tries, the whole thing fits in about twenty lines you can write from memory.

This guide builds DSU from the naive version up, explains why the optimisations work, and then solves the problem families in Java, C++ and Python.

What Problem Union-Find Solves

You have n elements, initially each in its own set. You receive a stream of operations:

• union(a, b): merge the set containing a with the set containing b.
• find(a): return an identifier for a's set, so that find(a) == find(b) tells you whether a and b are in the same set.

In graph language: vertices are elements, every union is an edge being added, and find answers "are these two vertices connected?" at any moment. A BFS/DFS can answer one connectivity question in O(V + E), but re-running it after every edge addition costs O(E·(V + E)) overall. DSU answers each in near-constant time.

What DSU cannot do: split sets, delete edges, or tell you the path between two elements. If the problem needs any of those, it is not (purely) a DSU problem.

From Naive to Near-Constant Time: The Two Optimisations

Version 1: parent pointers

Each element stores parent[x]; roots point to themselves. find walks up to the root; union sets one root's parent to the other. Simple, but unions like (0,1), (1,2), (2,3)... can build a chain of length n, making find O(n).

Optimisation 1: union by rank (or size)

Always attach the shorter tree under the taller one (rank is an upper bound on height), or the smaller tree under the larger one (size). A node's depth increases only when its tree is merged under a tree at least as large, which at least doubles the size of its tree. Since size cannot exceed n, depth is at most log₂ n. So find becomes O(log n) worst case.

Optimisation 2: path compression

During find(x), after locating the root, point every node on the path directly at the root. The next find on any of them is one step. Path compression alone gives O(log n) amortised per operation.

Both together: inverse Ackermann

Combining both gives O(α(n)) amortised per operation (Tarjan, 1975), where α is the inverse of the extremely fast-growing Ackermann function. α(n) ≤ 4 for any n you could ever store. In interviews, say: "amortised inverse Ackermann, effectively constant". You do not need to prove it; you do need to know which optimisation gives which bound.

Union-Find Template Code (Java, C++, Python)

This version uses union by size (handy because many problems ask for component sizes) and tracks the number of components.

class DSU {
    private final int[] parent, size;
    private int components;

    DSU(int n) {
        parent = new int[n];
        size = new int[n];
        components = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find(int x) {
        // iterative path compression: first find root, then repoint the path
        int root = x;
        while (parent[root] != root) root = parent[root];
        while (parent[x] != root) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;          // already connected
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;                     // attach smaller under larger
        size[ra] += size[rb];
        components--;
        return true;
    }

    boolean connected(int a, int b) { return find(a) == find(b); }
    int componentSize(int x) { return size[find(x)]; }
    int components() { return components; }
}

struct DSU {
    vector<int> parent, sz;
    int components;
    explicit DSU(int n) : parent(n), sz(n, 1), components(n) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];   // path halving: compresses as it walks
            x = parent[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
        components--;
        return true;
    }
};

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:            # compress the path
            self.parent[x], x = root, self.parent[x]
        return root

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

Three implementation notes. First, the C++ version uses path halving (each node points to its grandparent as you walk), which has the same amortised bound as full compression and needs no second loop. Second, the iterative finds avoid recursion depth problems; the common recursive one-liner parent[x] = find(parent[x]) is fine in Java and C++ but can hit Python's recursion limit before compression kicks in. Third, the Python tuple assignment self.parent[x], x = root, self.parent[x] evaluates the right side first, so it reads the old parent before overwriting; this is correct, but if it looks too clever in an interview, use a temporary variable.

Dry Run: Six Elements, Four Unions

n = 6, operations: union(0,1), union(2,3), union(1,3), union(4,5), then find(3), connected(0,5).

Notice how find(3) flattened the tree: before it, 3 was two steps from the root; afterwards, one. Over many operations this flattening is what makes the amortised cost nearly constant.

Undirected Cycle Detection: Redundant Connection (684)

A tree with n nodes got one extra edge. Return the edge that, if removed, leaves a tree (the last such edge in the input). Process edges in order: if union(u, v) returns false, u and v were already connected, so this edge closes a cycle. That is the answer.

public int[] findRedundantConnection(int[][] edges) {
    DSU dsu = new DSU(edges.length + 1);     // nodes are 1..n
    for (int[] e : edges) {
        if (!dsu.union(e[0], e[1])) return e;
    }
    return new int[0];
}

O(n · α(n)). The DFS alternative (for each edge, check whether u already reaches v before adding it) is O(n²). This is the cleanest demonstration of why DSU exists, and interviewers often use it as a warm-up before a harder DSU problem.

Redundant Connection II (685) is the directed version and much harder: the extra edge either gives some node two parents, or creates a cycle, or both. You track the two candidate edges for the double-parent node, try skipping the later one, and use DSU for the cycle check. Mention that it exists; detailed treatment rarely fits in 45 minutes. For directed cycles in general, use the techniques in topological sort.

Graph Valid Tree (261) is the same idea: n − 1 edges and no union returns false.

Kruskal's Minimum Spanning Tree with Union-Find

A minimum spanning tree connects all vertices of a weighted undirected graph with minimum total edge weight. Kruskal's algorithm: sort edges by weight; add each edge if it connects two different components; stop after V − 1 edges.

Why greedy works (cut property): for any partition of vertices into two sides, the lightest edge crossing the partition belongs to some MST. When Kruskal considers edge (u, v) and u, v are in different components, take the cut "u's component vs everything else". Every lighter edge was already considered and either added or skipped because it was inside a component, so no lighter edge crosses this cut. Hence (u, v) is the lightest crossing edge and safe to add. The general recipe for proofs like this is in how to know when greedy works.

Min Cost to Connect All Points (1584)

Points on a plane, cost is Manhattan distance, connect all at minimum cost. Build all n(n−1)/2 edges, sort, run Kruskal.

def min_cost_connect_points(points):
    n = len(points)
    edges = []
    for i in range(n):
        xi, yi = points[i]
        for j in range(i + 1, n):
            xj, yj = points[j]
            edges.append((abs(xi - xj) + abs(yi - yj), i, j))
    edges.sort()
    dsu = DSU(n)
    total = used = 0
    for w, u, v in edges:
        if dsu.union(u, v):
            total += w
            used += 1
            if used == n - 1:
                break
    return total

int minCostConnectPoints(vector<vector<int>>& points) {
    int n = points.size();
    vector<array<int, 3>> edges;
    edges.reserve((size_t)n * (n - 1) / 2);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            edges.push_back({abs(points[i][0] - points[j][0]) +
                             abs(points[i][1] - points[j][1]), i, j});
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    int total = 0, used = 0;
    for (auto& [w, u, v] : edges) {
        if (dsu.unite(u, v)) {
            total += w;
            if (++used == n - 1) break;
        }
    }
    return total;
}

Complexity: O(n² log n) for sorting n² edges. For this complete graph, Prim's algorithm with an O(n²) array (no heap, no edge list) is asymptotically better and uses O(n) memory. That is a great follow-up answer: "Kruskal is natural for sparse edge lists; for a dense complete graph, array-based Prim avoids materialising all edges."

Indian-context framing that works well in interviews: "Connect all Swiggy dark stores with the cheapest fibre network" or "lay pipelines between villages at minimum cost" are MST problems. Variants: Connecting Cities With Minimum Cost (1135), Optimize Water Distribution (1168) (add a virtual node 0 connected to each house with the well cost, then run Kruskal: a classic trick), and Find Critical and Pseudo-Critical Edges (1489).

Accounts Merge (721): Grouping by Equivalence

Each account is a name plus emails. Two accounts belong to the same person if they share any email. Merge them and output each person's sorted emails. The insight: emails are the elements; every account says "all these emails are equivalent". Union each email with the first email of its account, then group by root.

from collections import defaultdict

def accounts_merge(accounts):
    email_id = {}
    email_name = {}
    for acc in accounts:
        name = acc[0]
        for email in acc[1:]:
            if email not in email_id:
                email_id[email] = len(email_id)
                email_name[email] = name
    dsu = DSU(len(email_id))
    for acc in accounts:
        first = email_id[acc[1]]
        for email in acc[2:]:
            dsu.union(first, email_id[email])
    groups = defaultdict(list)
    for email, i in email_id.items():
        groups[dsu.find(i)].append(email)
    return [[email_name[emails[0]]] + sorted(emails) for emails in groups.values()]

public List<List<String>> accountsMerge(List<List<String>> accounts) {
    Map<String, Integer> id = new HashMap<>();
    Map<String, String> owner = new HashMap<>();
    for (List<String> acc : accounts)
        for (int i = 1; i < acc.size(); i++) {
            id.putIfAbsent(acc.get(i), id.size());
            owner.put(acc.get(i), acc.get(0));
        }
    DSU dsu = new DSU(id.size());
    for (List<String> acc : accounts)
        for (int i = 2; i < acc.size(); i++)
            dsu.union(id.get(acc.get(1)), id.get(acc.get(i)));
    Map<Integer, List<String>> groups = new HashMap<>();
    for (Map.Entry<String, Integer> e : id.entrySet())
        groups.computeIfAbsent(dsu.find(e.getValue()), k -> new ArrayList<>()).add(e.getKey());
    List<List<String>> res = new ArrayList<>();
    for (List<String> emails : groups.values()) {
        Collections.sort(emails);
        List<String> row = new ArrayList<>();
        row.add(owner.get(emails.get(0)));
        row.addAll(emails);
        res.add(row);
    }
    return res;
}

Complexity: O(E · α(E) + E log E) where E is the total number of emails; sorting dominates. Do not union by name: two different people can share a name. This "same name, different person" trap is deliberately in the problem, and noticing it out loud earns credit.

The same equivalence pattern solves Satisfiability of Equality Equations (990) (union all a==b first, then check that no a!=b has both sides in one set), Similar String Groups (839), Smallest String With Swaps (1202) (indices that can be swapped form components; sort characters within each component), and Synonymous Sentences (1258).

Counting Components as the Graph Changes

The components counter in the template starts at n and drops by one on each successful union. That makes "how many groups after each operation?" trivial.

Number of Islands II (305)

Start with all water; land is added one cell at a time. After each addition, report the island count. Re-running BFS per addition is O(k · R · C). With DSU: when a cell becomes land, increment the count, then union it with each land neighbour (each successful union decrements). Total O(k · α(R·C)). Map cell (r, c) to index r * C + c. Watch for duplicate additions of the same cell: skip them. The static version is covered in LeetCode 200 explained.

def num_islands2(m, n, positions):
    dsu = DSU(m * n)
    land = [[False] * n for _ in range(m)]
    count = 0
    res = []
    for r, c in positions:
        if land[r][c]:
            res.append(count)                # duplicate addition
            continue
        land[r][c] = True
        count += 1
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and land[nr][nc]:
                if dsu.union(r * n + c, nr * n + nc):
                    count -= 1
        res.append(count)
    return res

Most Stones Removed (947)

A stone can be removed if another stone shares its row or column. The maximum removable count is stones − components, because each connected group can be reduced to one stone. Trick: union the row and column themselves (treat row r as node r and column c as node c + 10001), so each stone is a union of its row and column. Count components among the touched nodes.

Weighted Union-Find: Evaluate Division (399)

Given equations like a / b = 2.0 and b / c = 3.0, answer queries like a / c. Each node stores weight[x] = x / parent[x]. After path compression, weight[x] = x / root, so a / c = weight[a] / weight[c] when they share a root.

def calc_equation(equations, values, queries):
    parent, weight = {}, {}

    def add(x):
        if x not in parent:
            parent[x] = x
            weight[x] = 1.0

    def find(x):
        if parent[x] != x:
            p = parent[x]
            parent[x] = find(p)          # after this, weight[p] = p / root
            weight[x] *= weight[p]       # x/p * p/root = x/root
        return parent[x]

    def union(a, b, val):                # a / b = val
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            weight[ra] = val * weight[b] / weight[a]   # ra / rb

    for (a, b), v in zip(equations, values):
        add(a); add(b)
        union(a, b, v)

    out = []
    for a, b in queries:
        if a not in parent or b not in parent or find(a) != find(b):
            out.append(-1.0)
        else:
            out.append(weight[a] / weight[b])
    return out

Derivation of the union formula, which interviewers may ask you to justify: we want ra / rb. We know a / ra = weight[a], b / rb = weight[b] and a / b = val. So ra / rb = (a / weight[a]) / (b / weight[b]) = val · weight[b] / weight[a]. The same structure with additive offsets instead of ratios solves "parity" and "distance to root" problems. A BFS over a ratio graph also solves Evaluate Division; weighted DSU is the faster, more elegant answer when queries are many.

Offline Queries: Sort, Then Union Incrementally

A powerful pattern: if queries ask "are u and v connected using only edges with weight below L?", sort the queries by L and the edges by weight. Sweep through queries in increasing L, unioning all edges lighter than the current limit before answering. Each edge is unioned once.

public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
    Arrays.sort(edgeList, (a, b) -> Integer.compare(a[2], b[2]));
    Integer[] order = new Integer[queries.length];
    for (int i = 0; i < order.length; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> Integer.compare(queries[a][2], queries[b][2]));
    DSU dsu = new DSU(n);
    boolean[] ans = new boolean[queries.length];
    int e = 0;
    for (int qi : order) {
        int limit = queries[qi][2];
        while (e < edgeList.length && edgeList[e][2] < limit) {
            dsu.union(edgeList[e][0], edgeList[e][1]);
            e++;
        }
        ans[qi] = dsu.connected(queries[qi][0], queries[qi][1]);
    }
    return ans;
}

O(E log E + Q log Q). The reverse trick handles deletions: if a problem removes edges over time and asks about connectivity, process operations backwards so removals become additions. Bricks Falling When Hit (803) is the famous hard example.

Union-Find vs BFS/DFS: When to Use Which

For the traversal side of the table, see graph BFS and DFS interview problems.

How Union-Find Shows Up in Interviews

DSU problems are popular at Google, Amazon and fintech companies like Razorpay and PhonePe, where entity resolution ("are these two user records the same person?") is a real business problem. Accounts Merge is literally a simplified KYC deduplication task. Interviewers typically probe:

• "What is the complexity?" Say O(α(n)) amortised with both optimisations, and explain which one gives what.
• "Why amortised?" A single find can still walk a long path once; compression ensures the total over m operations is O(m·α(n)).
• "Elements are strings, not integers." Map them to indices with a hash map, or implement DSU over a dictionary (as in Evaluate Division).
• "Can you do it without DSU?" For Accounts Merge, build a graph of emails and DFS. Showing both demonstrates range.
• "Scale it." At billions of records, entity resolution uses distributed connected-components algorithms (for example on Spark) with the same union idea applied in rounds.

Common Union-Find Mistakes

• Linking the elements instead of their roots. parent[a] = b without calling find corrupts the forest. Always find both roots first.
• Comparing parent[a] == parent[b] to check connectivity. Parents are not roots; use find.
• Reading size[x] instead of size[find(x)]. Only roots hold valid sizes.
• Grouping results by parent[i] at the end. Some nodes may not be compressed; call find(i) for each.
• Off-by-one with 1-indexed nodes (Redundant Connection). Allocate n + 1.
• Recursive find in Python on a long chain before any compression: RecursionError. Use iterative find or union by size, which bounds depth at log n.
• Using DSU for a directed problem. Union is symmetric; direction is lost.

Union-Find Practice List

Swim in Rising Water is a nice cross-over: the minimax Dijkstra solution and the "add cells in increasing height until start and end connect" DSU solution are both accepted, and discussing both is a strong interview move. For where DSU sits in an overall plan, see top DSA patterns for coding interviews.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.