Union Find

What is this?

Union-find answers "are these two things in the same group?" when groups only ever merge. The 301 twist is that nobody hands you the edges. You are given strings and told two belong together if one is a single swap from the other — so before any union can happen you must decide which pairs qualify, and that decision is where all the cost lives.

flowchart TD A["no edge list is given"] --> B["derive the edges"] B --> C{"which comparison is cheaper?"} C -->|"few strings, long"| D["compare every pair — O(n² · L)"] C -->|"many strings, short"| E["generate each string's swaps
and look them up — O(n · L²)"] D --> F["union the qualifying pairs"] E --> F F --> G["component counter = number of groups"]

💡 Fun fact: Similar String Groups has two correct solutions whose costs point in opposite directions, and choosing between them is the interview question. Comparing every pair costs O(n² · L); generating every single-swap variant of each string and looking it up costs O(n · L²). With many short strings the second wins, with a few long ones the first does. Being able to state both and pick against the stated constraints is worth more than implementing either well.

🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.

The one-line idea: union-find is the easy half. When the edges must be derived, the comparison strategy is the algorithm — choose its cost against the constraints rather than by habit.

1. The structure, and the counter

parent = list(range(n)); rank = [0] * n; groups = n

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]        # path halving
        x = parent[x]
    return x

def union(a, b):
    global groups
    ra, rb = find(a), find(b)
    if ra == rb: return False                # already together
    if rank[ra] < rank[rb]: ra, rb = rb, ra
    parent[rb] = ra
    if rank[ra] == rank[rb]: rank[ra] += 1
    groups -= 1
    return True

With path halving and union by rank the amortised cost is effectively constant, so the union-find is never the bottleneck here — the pair comparison is. A component counter that moves only on a real merge means the answer needs no final pass.

2. Deriving the edges

Two strings are similar if they are identical, or differ in exactly two positions whose characters are swapped:

def similar(a, b):
    diff = []
    for i, (x, y) in enumerate(zip(a, b)):
        if x != y:
            diff.append(i)
            if len(diff) > 2: return False        # a third difference is fatal
    return not diff or (a[diff[0]] == b[diff[1]] and a[diff[1]] == b[diff[0]])

The early exit matters: no single swap can reconcile three differing positions, so scanning further is wasted. The identical case — zero differences — is easy to forget and is explicitly similar.

3. A 30-second worked example

strs = ["tars", "rats", "arts", "star"]

tars vs rats:  diffs at [0, 2]        't','r' vs 'r','t'  swapped ✓  union
tars vs arts:  diffs at [0, 1, 2]     three differences   ✗
tars vs star:  diffs at [0, 1, 2, 3]                      ✗
rats vs arts:  diffs at [0, 1]        'r','a' vs 'a','r'  swapped ✓  union
rats vs star:  diffs at [0, 1, 2, 3]                      ✗
arts vs star:  diffs at [0, 1, 2, 3]                      ✗

components: {tars, rats, arts}  and  {star}      →  2 groups

The instructive pair is tars and arts. They are not similar — three positions
differ, and no single swap fixes three. Yet they end up in the same group, because
rats is similar to both. Similarity is not transitive; connectivity is, and that gap
is exactly why the problem needs union-find rather than a pairwise grouping.

4. Where you'll actually meet this

Record deduplication. Merging customer or product records that are "close enough", where closeness is computed rather than supplied.
Spell-check and fuzzy search. Grouping words within a bounded edit distance.
Bioinformatics. Clustering sequences differing by a limited number of mutations.
Network and fraud analysis. Connectivity over derived relationships — shared fingerprints, shared behaviour signatures.
Kruskal's algorithm. Minimum spanning trees union edges in weight order, skipping any whose endpoints already share a root.

5. Problems in this chapter

▶ Similar String Groups

Count groups of strings connected by single-swap similarity. Derive the edges by pairwise comparison or by generating swap variants, then union and read the component counter.
Pattern: union-find with computed edges. Target: O(n² · L) or O(n · L²) — chosen against the constraints.

6. Common pitfalls 🚫

Assuming similarity is transitive. It is not; connectivity through unions is what groups the strings.
Missing the identical case, which counts as similar with zero differences.
Accepting any two differences. The characters must be swapped, not merely unequal.
Not exiting early once a third difference appears.
Decrementing the component counter unconditionally rather than only on a real merge.
Skipping path compression, which turns near-constant operations linear on a degenerate chain.
Not stating the complexity trade-off. With two valid strategies, the interviewer is waiting for you to choose and justify.

7. Key takeaways

Union-find is the easy part. Deriving the edges carries the cost and the thinking.
Two strategies with opposite costs — pick against n versus L and say why.
Similarity is not transitive; connectivity is. That gap is the reason for the structure.
A component counter that moves only on real merges gives the answer for free.
Path compression plus union by rank makes the operations effectively constant.
Verify similarity by hand on a small case — the swap condition is stricter than it first reads.
Why interviewers like it: the data structure is textbook, so the conversation goes immediately to modelling and to justifying a complexity choice.

Order: Similar String Groups.

Advanced