222: Disjoint Set Union: Union-Find, Path Compression, Rank, and Connectivity

Learning outcomes

By the end of this lesson, you should be able to:

explain and apply a parent forest in a realistic implementation;
explain and apply path compression in a realistic implementation;
explain and apply union by rank or size in a realistic implementation;
explain and apply a component count in a realistic implementation;
explain and apply offline connectivity in a realistic implementation.

These are practical implementation skills, not just vocabulary. You should be able to describe the invariant behind each choice, recognize when DSU fits the operation pattern, and identify when its limitations mean you need another approach.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from a previous project where you had to maintain groups, equivalence, connectivity, or a changing set of relationships. It does not need to have been implemented with DSU. The point is to connect the abstract structure to a problem you have already seen.

The goal is not to memorize a few method names. It is to make a defensible decision in an interview-sized problem and in a production data-processing problem. That means reasoning from the constraints: which operations are supported, whether relationships only accumulate, how many elements exist, and what answer must be available after each operation.

Terminology

Parent forest: Each element points toward a representative root. The parent pointers form several trees, one tree per connected component, rather than one tree containing every element.
Path compression: During find, point visited nodes closer to, or directly at, the root so that later finds traverse much less structure. This changes the forest while preserving its component partition.
Union by rank or size: Attach the smaller or shallower tree under the larger or deeper root to avoid creating tall chains. The link must be made between roots, not arbitrary nodes.
Component count: Initialize the count to n, then decrement it only when a union merges two previously distinct roots. A union of two elements already in the same component does not change the count.
Offline connectivity: DSU handles edge additions and equivalence merging well. Arbitrary deletions are not a native fit; they require an offline/rebuild technique or a more advanced dynamic-connectivity structure.
Grid applications: Map cells to indices so the same component machinery can solve island merging, account grouping, redundant connections, and activation problems in which components evolve over time.

The word “root” is operationally important. A representative is not necessarily the smallest, oldest, or otherwise special element. It is simply the node currently serving as the root of that tree, and its identity may change when two components are merged.

Mental model

Treat Disjoint Set Union: Union-Find, Path Compression, Rank, and Connectivity as a design problem with observable inputs, outputs, invariants, and failure modes. DSU maintains a partition of elements under repeated union and find operations. It is especially useful for offline or incremental connectivity questions and for Kruskal-style cycle checks, where an edge is redundant if its endpoints already have the same representative.

For now, keep the model simple: every element belongs to exactly one component, every component has one root, and following parent pointers eventually reaches that root. A useful invariant is that parent pointers never form a cycle and that two elements are in the same component exactly when their find results are equal. Path compression can rewrite pointers, and union-by-rank or union-by-size can choose a different root, but neither operation is allowed to change which elements are connected.

A strong implementation makes assumptions visible, narrows uncertainty at boundaries, and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to show why the design is safe. A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call or a familiar template. First state what must remain true. Then choose the mechanism that enforces it. For example, if the requirement is to answer whether two accounts are connected after a stream of merges, DSU is a plausible model. If the requirement includes removing arbitrary edges and answering immediately after each removal, that is a different constraint and should be called out before implementation.

Deep dive

1. Parent forest

The naive representation is an array of parent pointers. A root points to itself, so an initially independent collection can be represented by parent[i] = i. Each element points toward a representative root, and find(x) follows those pointers until it reaches a node whose parent is itself. That representative must be consistent for all members of the same set at the time of the query.

The structure is called a forest because there may be several trees at once. union(a, b) finds both roots and links one root beneath the other. It should not link arbitrary nodes, because doing so makes the height and the correctness argument harder to control. The key invariant is that every link moves toward a root and never creates a cycle.

Decision rule: Use a parent forest deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. A parent array is an implementation mechanism, not a reason to use DSU; the operation requirements have to justify it.

2. Path compression

The problem with a plain parent forest is a long chain. If a points to b, which points to c, and so on, a single find(a) must walk every link. Repeating that query can make a structure that looked like constant-time lookup behave linearly in the height of the tree.

Path compression fixes the repeated-work part of that problem. While find walks from a node to its root, it rewrites the visited nodes to point directly to the root, or at least closer to it. The first lookup may still do substantial work; later lookups on the same path become much cheaper. This is a mutation of the representation, not a mutation of the connected components.

There is one subtle detail worth knowing: path compression is usually implemented recursively or with an iterative two-pass traversal. Whichever form you choose, it must return the root and update only valid parent links. It cannot compensate for an incorrectly initialized parent array or for out-of-range input.

Decision rule: Use path compression deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. When debugging, inspect the parent array before and after a repeated find; a compressed path should be flatter, while the representatives and component membership should be unchanged.

3. Union by rank or size

Even with correct roots, always attaching the second root beneath the first can create a tall chain. Union by rank or size prevents that predictable imbalance. With size, attach the root of the smaller component beneath the root of the larger component and update the larger size. With rank, maintain a height-related upper bound and attach the lower-rank root beneath the higher-rank root; increase the rank only when the ranks are equal.

The bookkeeping value is meaningful only at roots. After a union, the child root's stored size or rank should not be treated as the current component summary. Combined with path compression, this strategy gives the standard amortized complexity of O(alpha(n)) per operation, where alpha is the inverse Ackermann function and grows so slowly that the cost is effectively constant for practical input sizes. That is an amortized guarantee over a sequence of operations, not a claim that every individual call performs no work.

Decision rule: Use union by rank or size deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Pick one policy, maintain its metadata consistently, and test a tie case as well as a clearly larger-versus-smaller merge.

4. Component count

If n elements start independently, the component count begins at n. A union first finds the two representatives. If the representatives differ, the operation merges two components and decrements the count exactly once. If they are equal, the edge is redundant and the count stays the same.

This gives quick answers for connectivity milestones, such as “how many groups remain?” or “when did all active nodes become connected?” The count is derived from successful root merges, not from the number of union calls. Duplicate edges and cycles are therefore important tests: they must not make the count drift downward.

Decision rule: Use component count deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Keep the counter close to the merge decision so it cannot be decremented for a no-op union.

5. Offline connectivity

DSU is a strong fit when relationships are added over time or when a complete list of edges can be processed in an order that answers the question. It handles edge additions and equivalence merging easily. For example, process each edge, compare the two roots, and use the equality result to detect whether the edge closes a cycle.

Arbitrary deletions are the boundary. Removing an edge can split a component, but parent pointers do not contain enough information to cheaply reconstruct that split. If deletions are known ahead of time, an offline/rebuild strategy may work; otherwise, dynamic-connectivity structures are more appropriate. Do not describe DSU as a general-purpose graph update structure when its natural operation is monotonic merging.

Decision rule: Use offline connectivity deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Write down the operation order and whether answers are required online; those two details often determine whether DSU is valid.

6. Grid applications

Grid problems often look different from graph problems, but the representation is the same. Map a cell at row r and column c to a one-dimensional index such as r * columnCount + c. Activate or inspect only valid cells, then union neighboring active cells. DSU can consequently support island merging, account grouping, redundant connections, and activation problems where components evolve over time.

The boundaries need care: convert coordinates consistently, avoid joining blocked or inactive cells, and use the grid dimensions that belong to the current instance. A count of active components is not automatically the same as the count of all grid cells. This is also a useful place to measure storage: the parent and metadata arrays are proportional to the number of mapped cells, even if only a subset is active.

Decision rule: Use grid applications deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Test corners, repeated activation, blocked neighbors, and a grid with no active cells.

Worked example

Consider an interview-sized problem and a production data-processing problem. In both cases, begin by writing the requirement in one sentence, list the input and output contracts, and identify which concept above owns each failure mode. For a connectivity task, that might mean stating whether vertices are zero-based, whether duplicate edges are allowed, whether all vertices begin active, and whether deletions exist. Those details are not decoration; they determine whether the DSU invariant can be maintained.

The important move is separation. Parsing and validation belong at the boundary; domain rules belong in the domain or service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing these concerns can make a happy-path demo look shorter, but it makes malformed input, retries, and edge cases much harder to reason about. The DSU itself should receive a well-defined set of elements and own only the partition and merge/query invariants.

The following small function is not a DSU implementation. It is a reminder to state the invariant before selecting a data structure. Its loop invariant is that answer is the maximum value encountered so far. In a connectivity problem, the analogous discipline would be to state that every element reaches exactly one root and that the component count changes only after a successful merge.

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

There is an edge case hidden in this deliberately small example: with an empty array, it returns 0, which is only correct if the contract defines 0 as the empty-input result and the domain permits that default. A senior review would ask whether an empty or missing value should instead be rejected or represented with a different type. The code demonstrates invariant-first reasoning, but it should not be mistaken for a complete solution to a DSU problem.

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For each case, state which layer detects the problem and what the caller observes. For DSU, translate those cases into repeated edges, self-edges, invalid indices, and a failed upstream data source. This is the level of explanation expected in a senior code review or technical interview: name the contract, identify the owner, and describe the observable result rather than only showing the happy path.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. For DSU specifically, ask whether the structure is request-local or shared, whether concurrent mutation needs synchronization, whether indices can be trusted, and whether the parent and metadata arrays fit the memory budget. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted. DSU does not validate identity, authorization, or input by itself; it only maintains the relationships that the owning layer has accepted.

Guided lab

Implement DSU with size and path compression, use it to detect redundant edges and process “add land” island queries, and instrument tree height before and after compression. Start with the parent and size invariants, then make the mapping from each problem's input to DSU indices explicit. For “add land,” decide how repeated activation is handled before writing the union logic; otherwise a retry can incorrectly change the island count.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

When instrumenting height, distinguish the height before a find from the height after path compression. A successful compression should reduce traversal work on later queries; it should not change the reported connected components. Also check the no-op cases: a duplicate edge, a self-edge, and activation of an already active cell must not decrement the component count.

Edge cases and failure modes

Parent forest: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Also test invalid indices and verify that the implementation does not silently create a phantom component.
Path compression: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Inspect a deliberately deep path before and after find, while confirming that root identity and membership remain valid.
Union by rank or size: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include equal-rank or equal-size merges and verify that metadata is updated only for the surviving root.
Component count: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. A repeated union of already connected nodes must leave the count unchanged.
Offline connectivity: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Confirm that the chosen processing order matches the question and that arbitrary deletion has not been assumed away.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong. In DSU, this often appears as using a merge-only structure for a workload that requires deletions.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values. These choices can conceal invalid indices or an incorrect active-cell state until the component count is already wrong.
Testing only the happy path and therefore discovering contracts only after integration. Duplicate edges, self-edges, empty inputs, and repeated activation are part of the contract when the input can contain them.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement. Path compression and union by size are useful, but they do not remove the need to understand memory usage and operation order.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees. A client-reported relationship is still untrusted input.

For debugging, reproduce the smallest failing case, inspect the actual parent and metadata values or execution plan, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. If a component count is wrong, log each union's two roots and whether they were equal before the counter changed. If a lookup is unexpectedly slow, measure tree height and repeat the same find to determine whether compression is taking effect. For grid problems, inspect the coordinate-to-index mapping before inspecting the union logic.

Interview questions

What problem does Parent forest solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Path compression solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Union by rank or size solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Component count solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Offline connectivity solve, and what trade-off or failure mode would make you choose a different approach?

Answer these with more than a definition. State the supported operation pattern, the invariant, the relevant complexity, and one situation in which DSU is not enough. That is what distinguishes understanding the data structure from recalling its name.

Checkpoint

Without notes, explain Disjoint Set Union: Union-Find, Path Compression, Rank, and Connectivity to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code.

As a self-check, you should be able to explain why a successful union changes the component count, why a redundant union does not, what path compression changes internally, and why arbitrary deletion is outside the basic DSU model. If any of those answers is vague, return to the relevant deep-dive section before moving on.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.