DSU trick explainer

Disjoint Set Union is a way to keep track of which items belong to the same group after repeated merges. In coding interviews, it usually appears when a problem asks whether two positions are connected after many pairings. (cp-algorithms.com) The structure is also called Union-Find because its two core operations are “union,” which merges groups, and “find,” which returns a group’s representative. With path compression and union by rank or size, those operations run in nearly constant amortized time. (cp-algorithms.com, geeksforgeeks.org) LeetCode 1722 asks for the minimum Hamming distance between two arrays after any number of allowed swaps in the source array. The problem defines Hamming distance as the number of indices where `source[i]` and `target[i]` differ. (leetcode.com) The trick is to stop thinking about single swaps and start thinking about swap groups. If index 0 can swap with 2, and 2 can swap with 5, then 0, 2, and 5 form one connected component, and any value in that component can be rearranged within it. (algo.monster, cp-algorithms.com) That turns the problem into a counting exercise inside each component. For every connected group of indices, you count the values present in `source`, then try to match the values needed by `target`, and any leftover unmatched positions add to the final Hamming distance. (algo.monster, leetcode.doocs.org) The YouTube tutorial tied to this example walks through exactly that model: build components from `allowedSwaps`, bucket indices by parent, and compare value frequencies within each bucket. The video frames the method as a reusable pattern for interview problems built around connectivity rather than direct simulation. (youtube.com) That pattern shows up well beyond this one array problem. Disjoint Set Union is commonly used for connected components, cycle detection in undirected graphs, and any task where edges arrive one merge at a time and you need to answer “are these in the same set?” quickly. (cp-algorithms.com, geeksforgeeks.org) The interview lesson is that Disjoint Set Union is rarely the whole solution by itself. In LeetCode 1722, DSU finds which indices can mix; hash maps or counters do the rest by measuring how many values can actually be matched inside each connected group. (algo.monster, leetcode.ca) So the “DSU trick” is not swapping faster; it is recognizing when a long list of pairwise moves really defines a set of islands. Once the islands are built, the hard-looking problem often collapses into local counting inside each one. (cp-algorithms.com, algo.monster)