Union-Find (Disjoint Set) Pattern in Java - Interview Preparation Guide

Union-Find solves dynamic connectivity problems efficiently. It is the interview pattern for answering “are these items already in the same component?” while edges or relations keep arriving.

Strong candidates do not stop at naming DSU. They explain what the parent structure represents, why path compression matters, and when Union-Find is the right abstraction instead of DFS, BFS, or adjacency traversal.

Pattern Summary Table

Problem Statement

Given nodes and pairwise relations, determine connected components, detect redundant edges, or merge related groups efficiently.

Typical interview signals:

• edges are processed incrementally
• the key question is connectivity, not path shape
• repeated DFS or BFS would be too expensive
• the graph is undirected or the relation is equivalence-like

Pattern Recognition Signals

• Keywords in the problem: connected components, disjoint set, merge groups, redundant edge, connectivity queries.
• Structural signals: you care whether two items end up in the same group, not about the actual route between them.
• Complexity signal: many union or connectivity operations appear, so recomputing components from scratch is wasteful.

Visual Intuition

It supports two core operations:

• find(x) -> representative of component
• union(a, b) -> merge components

DSU Template

What we are doing actually:

1. Start with every node as its own parent.
2. find compresses paths so future lookups are faster.
3. union merges two roots and keeps the tree shallow with rank.

class DSU {
    int[] parent;
    int[] rank;

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

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

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;

        if (rank[ra] < rank[rb]) parent[ra] = rb; // Attach shallower tree under deeper tree.
        else if (rank[rb] < rank[ra]) parent[rb] = ra;
        else {
            parent[rb] = ra;
            rank[ra]++;
        }
        return true;
    }
}

Debug steps:

• print parent and rank after each union
• verify find flattens paths after repeated lookups
• test union on already-connected nodes

Problem 1: Number of Connected Components

Problem description: Count how many connected components remain after processing all undirected edges.

What we are doing actually:

1. Start with n separate components.
2. For each edge, try to union its endpoints.
3. Decrement the component count only when the union actually merges two roots.

public int countComponents(int n, int[][] edges) {
    DSU dsu = new DSU(n);
    int comps = n;
    for (int[] e : edges) {
        if (dsu.union(e[0], e[1])) comps--; // Successful merge reduces component count.
    }
    return comps;
}

Debug steps:

• print the roots before and after each edge union
• verify repeated edges do not decrement comps
• test no edges, one component, and multiple components

Problem 2: Redundant Connection

Problem description: Find the extra edge that creates a cycle in an otherwise tree-like graph.

What we are doing actually:

1. Process edges in order.
2. If both endpoints already share the same root, this edge is redundant.
3. Otherwise union them and continue.

public int[] findRedundantConnection(int[][] edges) {
    DSU dsu = new DSU(edges.length + 1);
    for (int[] e : edges) {
        if (!dsu.union(e[0], e[1])) return e; // This edge connects nodes already in same component.
    }
    return new int[0];
}

Debug steps:

• print roots of both endpoints before each union
• verify the first failed union is the returned answer
• watch indexing carefully because this problem is 1-based

Dry Run (Connected Components)

n = 5, edges: [0-1], [1-2], [3-4]

Initial components: 5

1. union(0,1) succeeds -> components 4
2. union(1,2) succeeds -> components 3
3. union(3,4) succeeds -> components 2

Final answer: 2 connected components.

Union only decreases component count when roots were different.

Problem 3: Accounts Merge

Use DSU to connect emails belonging to same user account, then group by root.

Common Mistakes

1. Missing path compression
2. Forgetting union by rank/size
3. 1-based vs 0-based indexing errors
4. Assuming DSU handles directed semantics directly

Pattern Variations

• union by size instead of rank
• string-key or email-key Union-Find via index compression or map-based IDs
• offline connectivity problems after sorting or batching queries

Pattern Composition (Advanced)

• Union-Find + hashmap for entity-to-index normalization
• Union-Find + sorting for Kruskal-style minimum spanning tree logic
• Union-Find + grouping pass after all unions to build final merged output

Debug Checklist

When DSU output is wrong:

1. print root of each node after all unions
2. verify index normalization (especially 1-based inputs)
3. confirm union returns false when already connected
4. ensure component count decrements only on successful union

Most DSU bugs are indexing or incorrect decrement logic.

Practice Problems

1. Redundant Connection (LC 684)
   LeetCode
2. Number of Connected Components in an Undirected Graph (LC 323)
   LeetCode
3. Accounts Merge (LC 721)
   LeetCode
4. Most Stones Removed with Same Row or Column (LC 947)
   LeetCode
5. Satisfiability of Equality Equations (LC 990)
   LeetCode

Key Takeaways

• Union-Find is for connectivity and grouping, not path exploration
• find must return stable representatives, and union must only reduce groups on real merges
• path compression and union by rank make the structure practically near-constant time
• most DSU bugs are indexing mistakes or incorrect component-count updates