Union-Find

Mental model

Union-Find tracks which items are in the same group with two operations: union(a, b) merges two groups, find(a) returns the group id. With path compression and union by rank, both run in essentially constant time. Use it whenever the question is "are these two in the same group?"

How to study Union-Find

Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use VisuAlgo — Union-Find Disjoint Sets to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.

Next, compare Union-Find with the neighboring concepts in its roadmap. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Union-find component count and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.

Proof of understanding

• Explain the mechanism from first principles and identify the state it reads or changes.
• Give one situation where the concept is the right choice and one where it is not.
• Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
• Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.

Learn from primary sources

• VisuAlgo — Union-Find Disjoint Sets (doc)

Practice and explain it back

Review prompts

• What do path compression and union by rank each contribute, and why is one alone not enough?

Build evidence

Use a roadmap capstone to turn this concept into working evidence.

Learning paths

• DSA Practice