Lesson 44Advanced58 minAssessment-backed

Union Find

Track connected components with near-constant union and find operations using parent links, path compression, and rank.

What you will be able to do

Explain disjoint sets and connected component tracking.

Implement find with path compression and union by rank/size.

Use union-find for redundant connection, account merging, and dynamic connectivity.

Compare union-find with BFS/DFS for repeated connectivity queries.

Identify when edge order or rollback requirements make union-find insufficient.

Union Find is the structure for repeatedly answering: are these two things in the same group? It is simple, fast, and central to connectivity problems.

Parent Links and Representatives

Each item points to a parent. The root representative names the set. Union connects representatives. Find returns the representative, compressing paths so future queries become faster.

Disjoint set forest — Union Find stores components as shallow parent trees.

Scenario: Account Merge

A product sees multiple accounts sharing emails, phone numbers, or verified identities. Union-find can merge records connected by shared identifiers, then group accounts by representative.

Need	Union-find fit	Caveat
Repeated connectivity	Excellent	Does not list path.
Merge accounts	Excellent	Identity rules must be precise.
Single traversal	DFS/BFS may be simpler	Union-find setup may be extra.
Delete/rollback edges	Not basic union-find	Needs advanced structure.

Path compression flattens parent links — Path compression makes future find calls cheaper.

Same Pattern in Java, Python, and JavaScript

Redundant connection: the first edge connecting two nodes already in the same component creates a cycle.

class UnionFind {
    int[] parent, rank;
    UnionFind(int n) { parent = new int[n + 1]; rank = new int[n + 1]; for (int i = 0; i <= n; i++) parent[i] = i; }
    int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); 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;
        else if (rank[ra] > rank[rb]) parent[rb] = ra;
        else { parent[rb] = ra; rank[ra]++; }
        return true;
    }
}

Assessment trap

Union-find answers component membership, not the actual path between two nodes. If the path matters, use graph traversal or store extra structure.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

Support find and union with near-constant amortized time.
Given edges of an undirected graph, return the edge that creates a cycle.
Return the number of connected components in an undirected graph.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Example	Brute-force approach	Stronger solution	Production notes
Account merge	Repeatedly DFS from every account.	Union accounts sharing verified identifiers, then group by root.	Identity rules matter more than the data structure.
Network connectivity	Run BFS for every connectivity query.	Union edges once and answer same-component queries with find.	Use traversal if actual path is needed.
Fraud rings	Merge related entities as signals arrive.	Union related nodes and monitor component sizes.	Deletions/rollback need advanced handling.

Solved modelInterview Question Solutions

Question 1: Implement Union Find

Support find and union with near-constant amortized time. Path compression flattens reads, and union by rank/size prevents tall trees from forming.

class UnionFind {
    int[] parent, rank;
    UnionFind(int n) { parent = new int[n + 1]; rank = new int[n + 1]; for (int i = 0; i <= n; i++) parent[i] = i; }
    int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); 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;
        else if (rank[ra] > rank[rb]) parent[rb] = ra;
        else { parent[rb] = ra; rank[ra]++; }
        return true;
    }
}

Question 2: Redundant Connection

Given edges of an undirected graph, return the edge that creates a cycle. Union each edge. The first edge connecting two already-connected nodes is redundant.

class RedundantConnection { int[] parent; int[] findRedundantConnection(int[][] edges) { parent = new int[edges.length + 1]; for (int i = 0; i < parent.length; i++) parent[i] = i; for (int[] e : edges) if (!union(e[0], e[1])) return e; return new int[0]; } int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); } boolean union(int a, int b) { int ra = find(a), rb = find(b); if (ra == rb) return false; parent[rb] = ra; return true; } }

Question 3: Number of Connected Components

Return the number of connected components in an undirected graph. Start with n components. Every successful union reduces the component count by one.

class Components { static int count(int n, int[][] edges) { int[] parent = new int[n], rank = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; int components = n; for (int[] e : edges) if (union(e[0], e[1], parent, rank)) components--; return components; } static int find(int x, int[] p) { return p[x] == x ? x : (p[x] = find(p[x], p)); } static boolean union(int a, int b, int[] p, int[] r) { int ra = find(a, p), rb = find(b, p); if (ra == rb) return false; if (r[ra] < r[rb]) p[ra] = rb; else if (r[ra] > r[rb]) p[rb] = ra; else { p[rb] = ra; r[ra]++; } return true; } }

Solved modelWorked Interview Answer

Implement union-find with path compression and union by rank. Path compression flattens trees during find; rank keeps unions shallow. Together they make operations near-constant amortized time.

class UnionFind {
    int[] parent, rank;
    UnionFind(int n) { parent = new int[n + 1]; rank = new int[n + 1]; for (int i = 0; i <= n; i++) parent[i] = i; }
    int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); 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;
        else if (rank[ra] > rank[rb]) parent[rb] = ra;
        else { parent[rb] = ra; rank[ra]++; }
        return true;
    }
}

Hands-on drillTry It Yourself

Practice task

Start with nodes 1..5. Union (1,2), (3,4), (2,3). Draw parent arrays before and after path compression.

Failure patternsCommon Mistakes to Avoid

Forgetting path compression.
Forgetting union by rank/size.
Using union-find when path reconstruction is required.
Ignoring dynamic deletion requirements.
Mixing 0-based and 1-based node IDs.

Execution guardrailQuick-Start Checklist

Initialize parent.
Implement find with compression.
Implement union by rank or size.
Return false when roots already match.
Track component count if needed.
State near-constant amortized cost.

Recall drillKnowledge Check

Question	Strong answer
What does find return?	The representative/root of a set.
What does union do?	Merges two sets if their roots differ.
What is path compression?	Pointing nodes directly to root during find.

VocabularyKey Terms

Term	Meaning
Disjoint set	Collection of non-overlapping groups.
Representative	Root that identifies a set.
Path compression	Flattening parent chains.
Union by rank	Attach shallower tree under deeper tree.

Next practiceFurther Reading

Practice redundant connection, accounts merge, connected components, and Kruskal MST.
Compare DFS/BFS with union-find.
Study rollback union-find only after basics.

Topological Sort

Trie and Prefix Systems