Union Find Pattern

Why this pattern matters for LeetCode

Counting connected components can be done with BFS or DFS, but that's O(V + E) per query. If the graph changes (edges added dynamically) or you need to answer 'are these two nodes connected?' after each update, re-running BFS every time is too slow. Union Find answers connectivity queries in near-constant time using path compression and union by rank. The two operations: find (which group does this element belong to?) and union (merge these two groups into one). These run in amortized O(α(n)) time, effectively O(1) for all practical inputs.

What the Union Find pattern is

Union Find (Disjoint Set Union) maintains a collection of disjoint groups. Each group has a representative (root). find(x) returns the root of x's group by following parent pointers up the chain. union(x, y) merges the two groups by connecting one root to the other. Path compression (updating every node's parent to point directly to the root during find) and union by rank (always attaching the smaller tree under the larger) keep the structure nearly flat, making operations nearly O(1).

Reach for Union Find when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Union Find

• ✓Number of Connected Components, start with n groups, merge as you process edges, read the final count
• ✓Redundant Connection, the first edge where both endpoints share a group creates a cycle
• ✓Graph Valid Tree, n nodes and n-1 edges with no cycle equals a valid tree
• ✓Accounts Merge, merge accounts that share an email address
• ✓Making a Large Island, precompute island sizes in a grid using Union Find

When NOT to use Union Find

• ✕The graph is static and you only need one traversal, standard BFS/DFS is simpler
• ✕You need shortest paths. Union Find tracks connectivity only, not distances
• ✕You need to split groups apart. Union Find supports merging but not splitting
• ✕The problem involves directed graphs. Union Find is for undirected connectivity

Better alternative: In those cases, BFS/DFS (for static graphs or path finding) or Dijkstra (for weighted shortest paths) is more appropriate.

JavaScript code template

Union Find with path compression and union by rank. O(α(n)) per operation

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i); // each node is its own root
    this.rank = new Array(n).fill(0);
    this.components = n; // track number of disjoint groups
  }

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

  union(x, y) {
    const px = this.find(x);
    const py = this.find(y);
    if (px === py) return false; // already in the same group, adding this edge creates a cycle

    if (this.rank[px] < this.rank[py]) {
      this.parent[px] = py;
    } else if (this.rank[px] > this.rank[py]) {
      this.parent[py] = px;
    } else {
      this.parent[py] = px;
      this.rank[px]++;
    }
    this.components--;
    return true; // successfully merged two groups
  }
}

parent[i] starts as i, every node is its own group. find() follows parent pointers to the root. Path compression sets parent[x] directly to the root on the way back, flattening the tree so future finds are faster. union() finds both roots and merges the smaller-rank tree under the larger-rank tree. components decrements on each successful merge. To count connected components: start with n groups, merge as you process edges, and read components at the end.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Initialize: parent[i] = i for all i. rank[i] = 0. components = n.
2. 2For each edge (u, v): call find(u) and find(v) to get their group roots.
3. 3If both roots are the same, u and v are already connected, adding this edge creates a cycle.
4. 4If roots differ, merge: attach the smaller-rank root under the larger-rank root. Decrement components.
5. 5After all edges: components holds the number of connected groups. union() returning false signals a cycle.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

Coming soon

• Number of Connected Components

  Initialize n components. Process each edge with union(). The final components count is the answer.

  Coming soon
• Redundant Connection

  The first edge where union() returns false (both nodes already connected) is the redundant edge creating a cycle.

  Coming soon
• Graph Valid Tree

  A valid tree has n-1 edges and no cycles. Use Union Find: n-1 successful unions with no cycle detected.

  Coming soon
• Accounts Merge

  Each email maps to a node. Union emails belonging to the same account. Group all emails by their root representative.

  Coming soon

Common mistakes beginners make

• ✕Skipping path compression, without it, find() can degrade to O(n) per call on a long chain. Always set parent[x] to the root on the way back up the recursion.
• ✕Comparing nodes directly instead of their roots, two nodes are in the same group if find(x) === find(y), not if x === y.
• ✕Forgetting to decrement components on a successful union, if you're counting components, every successful merge reduces the count by 1.
• ✕Using Union Find for directed graphs. Union Find tracks undirected connectivity. For directed cycle detection, use DFS or topological sort.

Union Find vs BFS/DFS for connectivity

Choose the right tool for the job.

Time and space complexity

α(n) is the inverse Ackermann function, it grows so slowly it's effectively constant (≤ 5) for any realistic input size. This near-constant cost comes from path compression (flattening the tree during find) and union by rank (preventing the tree from growing tall). Space is O(n) for the parent and rank arrays.

Frequently asked questions

What's the difference between Union Find and BFS for connectivity?

BFS explores a graph in O(V + E) and finds all connected components in one full pass. Union Find answers individual 'are these two nodes connected?' queries in near-constant time, even as edges are added dynamically. If the graph is static and you need one full scan, BFS is simpler. If you need many individual connectivity queries or dynamic updates, Union Find is faster.

What is path compression and why does it matter?

Without path compression, find() follows a chain of parent pointers to the root, this can be O(n) for a long chain. Path compression sets each visited node's parent directly to the root on the way back from the recursive call. The next find() on any of those nodes hits the root in one hop instead of traversing the whole chain.

What is union by rank?

Rank is an upper bound on the height of a tree rooted at a node. When merging two trees, attach the shorter tree (lower rank) under the taller tree (higher rank). This prevents the tree from growing tall and keeps find() fast. Without union by rank, repeated unions can create a linear chain. O(n) per find().

When does union() return false?

When both nodes are already in the same component, find(x) === find(y). Adding an edge between them would create a cycle. Redundant Connection specifically asks for the first edge where union() returns false.