Picture a party where you keep introducing people. Every time you introduce two strangers, their two friend circles merge into one. At any moment, you might ask "are these two people in the same friend circle now?" Union-Find (Disjoint Set Union, or DSU) answers exactly that question, and merges groups, both in near-constant time. It replaces slower BFS/DFS connectivity checks, and it's the difference between a working solution and a timeout on problems where connections arrive one at a time, like Number of Islands II.

Find: walking up to the group's leader, with a shortcut

find(x) walks up parent pointers from x until it reaches the root of x's tree, a node that is its own parent. That root acts as the "name" of the whole group. Without any optimization, this walk can take O(n) steps on a long, chain-like tree. Path compression fixes that: while walking up to find the root, rewire every node you pass through to point directly at the root. The next find call through any of those nodes is then instant.

This looks like a simple recursive one-liner, but it does real work: the recursive call returns the root, and the assignment flattens x's pointer to point straight at that root, permanently shortening the path for every future call that passes through x.

Remember: find() walks up to the root. Path compression rewires every node it passes through to point directly at that root, so the next lookup is instant.

Union by rank: keep the merged tree shallow

union(x, y) merges the two groups containing x and y by attaching one tree's root under the other's. Attaching them arbitrarily can, over many merges, build a tall, unbalanced tree. Union by rank (or by size) always attaches the shorter tree under the taller one's root, keeping the whole structure shallow.

Combined, path compression and union by rank give an amortized time of O(α(n)) per operation, where α is the inverse Ackermann function. For any n you could realistically encounter, α(n) is at most 4, which is why this is described as "nearly O(1)."

Remember: always attach the shorter tree under the taller one's root. Combined with path compression, this makes every operation nearly O(1).

Using union-find to catch a cycle as you build a graph

DSU gives a clean way to detect a cycle while building a graph one edge at a time: before adding an edge (u, v), check whether find(u) == find(v). If they're already in the same group, this edge would create a cycle, so either skip it, or, if you add it anyway, you've just confirmed a cycle exists. This is exactly how Kruskal's minimum-spanning-tree algorithm decides which edges to keep, and it's the core trick behind Graph Valid Tree below.

Remember: if find(u) equals find(v) before you union them, adding that edge would close a cycle.

Number of Connected Components in an Undirected Graph

LeetCode 323 · Number of Connected Components · DSU

Start with n components, since every node begins isolated. Each edge that connects two different components reduces the component count by exactly one; an edge between two nodes already in the same component changes nothing.

Approach: Initialize DSU with n singleton sets. Union across every edge; decrement a running count directly whenever a union actually merges two different roots.

Complexity: O(n + E · α(n)) time, O(n) space. This DSU class is the reusable template for all four problems in this lesson.

Common mistakes: Recomputing the component count with a separate pass calling find(i) on every node, instead of tracking it incrementally inside union. Forgetting path compression, which degrades find to O(n) on adversarial inputs, such as a chain graph.

Remember: start every node as its own component, then decrement the count by exactly one on every union that actually merges two different roots.

Longest Consecutive Sequence

LeetCode 128 · Longest Consecutive Sequence · DSU

Values that are consecutive integers (x and x+1) belong in the same "run." Union every value with value + 1 whenever that neighbor is present in the array; the answer is then the size of the largest resulting component. (A hash-set expand-from-start approach is O(n) and usually the preferred interview answer, but DSU is worth knowing since it's this lesson's topic, and the same "union adjacent related values" idea shows up elsewhere.)

Approach: Map each value to an index. Union value with value + 1 whenever both are present. Track component sizes in the DSU so "largest run" is a direct lookup.

Complexity: O(n · α(n)) time, O(n) space. The pure hash-set approach (expand upward only from numbers that have no num - 1 predecessor) reaches plain O(n) without any DSU overhead. Mention both, and lead with whichever fits the interviewer's follow-up.

Common mistakes: Unioning by raw value instead of by index, since the DSU arrays are indexed 0..n-1, not by arbitrary integer value. Forgetting to dedupe the input first, which wastes work reprocessing duplicate values.

Remember: union each value with value+1 when both exist; the biggest resulting group size is the longest consecutive run.

Graph Valid Tree

LeetCode 261 · Graph Valid Tree · DSU

A graph with n nodes is a valid tree only if it has exactly n - 1 edges AND is fully connected, meaning no cycles and no separate pieces. DSU checks both conditions in one pass: if any edge connects two nodes already in the same component, that's a cycle, and the graph is immediately invalid.

Approach: A quick edge-count check first (len(edges) != n - 1 fails immediately, saving wasted DSU work). Then union each edge, failing fast the moment a cycle is detected.

Complexity: O(n · α(n)) time, O(n) space.

Common mistakes: Skipping the len(edges) != n - 1 pre-check and relying purely on cycle detection: a graph can be cycle-free but still disconnected (a forest of separate trees), and the edge-count check is what rules that out cheaply. Forgetting that a valid tree also requires full connectivity, not just the absence of cycles.

Remember: a valid tree needs exactly n-1 edges AND no cycle. The edge count alone doesn't guarantee connectivity, and no-cycle alone doesn't either; you need both checks.

Number of Islands II

LeetCode 305 · Number of Islands II · DSU · Hard

Land cells are added one at a time, and after each addition you need the current island count. Recomputing with BFS/DFS after every single addition costs O(n) per query. DSU processes each addition in near-O(1), which is the entire reason DSU exists for dynamic (incremental) connectivity problems, as opposed to static ones where BFS/DFS is simpler.

Approach: Maintain a DSU over the grid's flattened cell indices, plus a land set tracking which cells are filled. On each new land cell, increment the island count by 1 (a brand-new component), then union with any of its 4 already-land neighbors, decrementing the count once per successful merge.

Complexity: O(k · α(k)) time for k position updates, O(k) space (only land cells get DSU entries, via a dict-based sparse DSU, not a full m*n array).

Common mistakes: Allocating a dense parent array of size m*n when a dict keyed by only the cells actually visited is simpler and avoids wasted memory on large sparse grids. Forgetting to handle duplicate positions in the input, since the same cell can appear twice and must not be double-counted as a new island. Not decrementing count on every successful union; each merge reduces the island count by exactly one, and a single new cell can merge with up to 4 neighbors at once.

Remember: each new land cell starts as its own island (+1), then merges with any land neighbors (-1 per merge). A sparse dict-based DSU avoids allocating the whole grid upfront.

The four problems in this lesson split along one axis: is the graph built once (Number of Connected Components, Graph Valid Tree), or does it grow incrementally (Longest Consecutive Sequence's value-by-value unions, Number of Islands II's cell-by-cell additions)? For the one-time case, BFS/DFS is usually just as good as DSU, and sometimes simpler to write. DSU earns its place specifically when connectivity needs to be checked between additions, not only once at the very end.