Pattern 17: Union-Find (Disjoint Set Union — DSU)

0. The Template (Copy-Paste Skeleton)

One class. Memorise it verbatim — it’s ~20 lines and it solves an entire category of graph problems that would otherwise need DFS plus bookkeeping.

// TEMPLATE — DSU with PATH COMPRESSION + UNION BY RANK  → ~O(1) amortised per operation
class DSU {
    private final int[] parent, rank;
    private int components;                       // handy for "how many groups?" questions

    DSU(int n) {
        parent = new int[n];
        rank   = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;   // everyone starts as their own root
        components = n;
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);   // PATH COMPRESSION: flatten on the way back
        return parent[x];
    }

    /** @return false if x and y were ALREADY connected (⇒ this edge closes a cycle) */
    boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;

        if (rank[rx] < rank[ry])       parent[rx] = ry;     // UNION BY RANK: hang the
        else if (rank[rx] > rank[ry])  parent[ry] = rx;     // shorter tree under the taller
        else { parent[ry] = rx; rank[rx]++; }               // equal → pick one, bump its rank

        components--;
        return true;
    }

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

// GRID VARIANT — map a 2-D cell to a 1-D id
int id(int r, int c, int cols) { return r * cols + c; }
// then union each cell with its right and down neighbours only (avoids doing every edge twice)

The two optimisations — and why you must have both

• Path compression (parent[x] = find(parent[x])) flattens the tree during lookup, so the next find on any node in that chain is O(1).
• Union by rank never hangs a taller tree under a shorter one, keeping depth logarithmic even before compression.
• Together they give O(α(n)) amortised — the inverse Ackermann function, which is < 5 for any n you can physically store. Effectively constant. With neither, a chain of unions degenerates to a linked list and find becomes O(n). Name this tradeoff in the interview.

union returning boolean is the whole trick

union(x, y) == false means x and y were already in the same component, so the edge you just tried to add creates a cycle. That single return value solves:

• LC 684 Redundant Connection — the first edge that returns false is the answer
• LC 261 Graph Valid Tree — valid iff no union fails and components == 1 at the end
• Kruskal’s MST — sort edges by weight, keep every edge whose union succeeds

When to reach for DSU instead of DFS

Situation	Use
edges arrive incrementally, query connectivity as you go	DSU — DFS would rerun from scratch
“how many connected components” on a static graph	either; DFS is fine
cycle detection in an undirected graph	DSU (directed → DFS colours or Kahn’s)
Kruskal’s minimum spanning tree	DSU (it’s a required component)
you need the actual path between two nodes	DFS/BFS — DSU knows whether, never how
accounts merge / friend circles / equations equality (LC 721, 990)	DSU

DSU answers “are these connected?” — it cannot give you a path, a distance, or an order. Deletion is also not supported: DSU is union-only, never split.

---

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

• “Are two elements in the same group / component / network?”
• “How many connected components?”
• “Dynamic connectivity” — edges arrive one at a time, answer queries as you go
• “Detect a cycle in an undirected graph”
• “Number of provinces / friend circles / islands joined by edges”
• “Account merge / email merge”
• Anything about equivalence classes (a == b, b == c ⇒ a == c)

If the problem is graph-shaped AND you only need group-membership (not paths), Union-Find usually beats BFS/DFS in both code length and runtime.

The Algorithm (Pseudocode)

parent[i] = i        // every node is its own root initially
rank[i]   = 0        // tree height (or size) for tie-breaking

find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   // path compression (one-pass)
        x = parent[x]
    return x

union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry: return false          // already connected → cycle if undirected
    if rank[rx] < rank[ry]:  parent[rx] = ry
    elif rank[rx] > rank[ry]: parent[ry] = rx
    else:                     parent[ry] = rx; rank[rx]++
    return true

The ‘Trick’ to Know

• Always use BOTH path compression (in find) AND union by rank/size (in union). With both, every op is ~O(α(n)) ≈ O(1) amortized (inverse Ackermann — effectively constant for any n ≤ 10⁶⁰⁰⁰).
• Number of components = number of i where parent[i] == i after all unions, OR maintain a count variable decremented on each successful union.
• For grid problems (LC 200 / 305), map (r, c) → r * cols + c to flatten to 1D ids.

---

2. Java Implementation (Brute Force vs. Optimal)

Example Problem: Number of Connected Components in an Undirected Graph — LC 323

Brute Force: DFS — O(V + E)

class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        boolean[] seen = new boolean[n];
        int components = 0;
        for (int i = 0; i < n; i++) {
            if (!seen[i]) { dfs(i, adj, seen); components++; }
        }
        return components;
    }
    private void dfs(int u, List<List<Integer>> adj, boolean[] seen) {
        seen[u] = true;
        for (int v : adj.get(u)) if (!seen[v]) dfs(v, adj, seen);
    }
}

Optimal: Union-Find — O(E · α(V))

class Solution {
    public int countComponents(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        for (int[] e : edges) uf.union(e[0], e[1]);
        return uf.count;
    }
}

class UnionFind {
    int[] parent;
    int[] rank;
    int count;

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

    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];   // path compression
            x = parent[x];
        }
        return x;
    }

    boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;          // already in same set
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[rx] > rank[ry]) parent[ry] = rx;
        else { parent[ry] = rx; rank[rx]++; }
        count--;
        return true;
    }
}

Java Architecture Insights

• Why int[] over Map<Integer,Integer>: int arrays are 4–8× faster (cache-friendly, no boxing). Use a map only when ids aren’t 0…n-1 (e.g., string ids — wrap a HashMap<String,Integer> indexer).
• Iterative find over recursive: recursive find with path compression is cleaner but blows the stack on long chains (LC 1971 with n = 10⁵ has triggered StackOverflowError). Iterative two-pass or one-pass halving is safer.
• Union by rank vs union by size: both give the same α(n) bound. Size is easier to reason about when you also need component size — store it in the same array (size[root] only valid if parent[root] == root).
• Encapsulate as a nested class in the same file — interviewers expect to see DSU as a reusable component, not inlined into main.

---

3. Mental Model & Visualization

ASCII Diagram (forest of trees)

Start: each node is its own tree
  0   1   2   3   4   5

union(0,1):              union(2,3):           union(0,2):
    1                        3                     1
    |                        |                     |
    0                        2                     0
                                                   |
                                                   3
                                                   |
                                                   2

find(2) walks: 2 → 3 → 0 → 1 (root)
Path compression flattens to: 2 → 1 directly

Senior Mental Trigger

“Dynamic connectivity, equivalence classes, or ‘how many groups?’ — reach for Union-Find before BFS/DFS. Path compression + union-by-rank = ~O(1).”

---

4. Curated Problem Lists

Commonly Asked (Bread & Butter)

#	Problem	Difficulty
LC 547	Number of Provinces	Medium
LC 323	Number of Connected Components in Undirected Graph	Medium
LC 200	Number of Islands	Medium
LC 684	Redundant Connection	Medium
LC 261	Graph Valid Tree	Medium
LC 990	Satisfiability of Equality Equations	Medium

FAANG ‘Aha!’ Level (Hard / Unintuitive)

#	Problem	Difficulty	Note
LC 721	Accounts Merge	Medium	Map<email, id> + DSU
LC 305	Number of Islands II	Hard	LC Premium — Dynamic DSU on grid
LC 1319	Number of Operations to Make Network Connected	Medium	Components - 1 ≤ extra edges?
LC 1971	Find If Path Exists in Graph	Easy	Iterative find mandatory at scale
LC 952	Largest Component Size by Common Factor	Hard	DSU + prime-factor bucket
LC 685	Redundant Connection II	Hard	Directed graph — pick which edge
LC 1101	The Earliest Moment Everyone Become Friends	Medium	Sort events, union, watch count
LC 128	Longest Consecutive Sequence	Medium	DSU variant (HashMap-based)

Frequency at MAANG (2026)

Pattern usage	Amazon	Meta	Google	Apple	Netflix
Union-Find	★	★★★	★★★	★	★

Meta and Google love this one. Number of Provinces and Accounts Merge are recurring at Meta.

---

5. Time & Space Complexity Table

Op	Naive Tree	+ Path Compression	+ Union by Rank/Size	Both (Optimal)
find	O(n)	O(log n) amortized	O(log n)	O(α(n)) ≈ 1
union	O(n)	O(log n)	O(log n)	O(α(n)) ≈ 1
Space	O(n)	O(n)	O(n)	O(n)

For n = 10⁸, α(n) ≤ 4. Treat as constant.

---

6. Common Variants & Extensions

Variant	Tweak to base DSU	Sample problem
Component size	maintain size[root]; expose getSize(x)	LC 952, LC 1319
Weighted DSU	track relative weight w[x] along parent edges	LC 399 Evaluate Division
String/Object ids	HashMap<String,Integer> id, assign on first sight	LC 721 Accounts Merge
Rollback / persistent DSU	use union-by-rank only (no path compression); push to stack	offline queries, competitive only
DSU on grid	flatten (r,c) → r*cols+c, union 4-neighbours	LC 200, LC 305
DSU with offline edges	sort edges by weight, union in order (= Kruskal’s)	Kruskal MST

---

7. Interview Red Flags & Gotchas

• ❌ Forgetting path compression — your O(α) blows up to O(log n) (still passes, but interviewer probes)
• ❌ Recursive find on n = 10⁵+ — StackOverflowError
• ❌ Returning void from union — losing the “was it a new union?” signal is the #1 cause of bugs in cycle-detection and component-count problems
• ❌ Confusing “directed” with “undirected” cycle detection — DSU works for undirected only; for directed use DFS coloring
• ❌ Using DSU for shortest-path or “find the actual edges” — wrong tool, use BFS/DFS/Dijkstra
• ❌ Resetting count outside the union method — keep it inside so the invariant holds

---

8. Companion 90-second Pitch (verbal)

“When I see dynamic connectivity — edges arriving, queries like ‘are X and Y in the same group’ or ‘how many groups’ — I reach for Union-Find. I keep a parent array and a rank array. find walks to the root with path compression, union joins roots by rank. Each op is effectively constant time, inverse-Ackermann. I’d code it as a small nested DSU class so it’s reusable and the interviewer sees the abstraction.”

Use this as a 90-second opener whenever the prompt smells like Union-Find — it signals seniority before you write a line.