Skip to content
Hello Python
Algorithm1 Practice1 Interview

Union-Find

Maintain dynamic components using path-compressed find and union by rank or size. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Union-Find when the prompt's constraints and required operations match this shape: Maintain dynamic components using path-compressed find and union by rank or size.

Pybit demonstrates Union-Find in a professional Python interview workspace.
On this page · Represent Components by Roots

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Union-Find Code Labs

Represent Components by Roots

Union-find stores a parent forest where each component has one root that parents itself. Two nodes are connected exactly when find returns the same root.

Compress Paths During Find

Path compression rewires visited nodes toward the root, preserving component identity while accelerating later queries. Apply it consistently in recursive or iterative find.

Trace Union-Find State

Reference
def union_find_trace(n,edges):
    parent=list(range(n));size=[1]*n;trace=[]
    def find(node):
        while node!=parent[node]:parent[node]=parent[parent[node]];node=parent[node]
        return node
    for left,right in edges:
        a,b=find(left),find(right);merged=a!=b
        if merged:
            if size[a]<size[b]:a,b=b,a
            parent[b]=a;size[a]+=size[b]
        trace.append([parent.copy(),size.copy(),merged])
    return trace
Practice

Implement union_find_trace(n,edges). Return [parent,size,merged] after each union using path compression and union by size.

Public tests

  • Attach smaller roots once

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Union Smaller Trees Under Larger

Union by size or rank attaches the shallower structure under the stronger root. Update metadata only on roots and only when two distinct components actually merge.

Find the First Redundant Edge

Reference
def first_redundant_edge(n,edges):
    parent=list(range(n));size=[1]*n
    def find(node):
        if parent[node]!=node:parent[node]=find(parent[node])
        return parent[node]
    for left,right in edges:
        a,b=find(left),find(right)
        if a==b:return [left,right]
        if size[a]<size[b]:a,b=b,a
        parent[b]=a;size[a]+=size[b]
    return []
Practice

Implement first_redundant_edge(n,edges). Return the first edge whose endpoints are already connected, or [].

Public tests

  • Reject an edge inside one component

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Use Union Find for Incremental Connectivity

Union-find excels at edge additions and repeated connectivity queries, with near-constant amortized operations. It does not directly support deletions, shortest paths, or component traversal; graph search is better for those.

Explain It in an Interview

Say: “Parent roots identify components. Find compresses paths, union attaches the smaller root, and an edge between equal roots is redundant.” State O((n + m) alpha(n)) time and O(n) space.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Union-Find complete workflowO((n + e) alpha(n))O((n + e) alpha(n))Use path-compressed find and union by size while maintaining a component counter.

Space

O(n) for the focused Count Components with Union-Find implementation.

Assumptions

  • Each root represents exactly one component. A union of distinct roots combines exactly two components, so decrementing once preserves the count; redundant edges do not change it.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Union-Find invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. Each element reaches exactly one representative for its component.
  3. A merge reduces the component count only when the representatives differ.
  4. Represent each component by one root. Preserve this claim after every transition.
  5. Decrement the count only when two distinct roots merge. Preserve this claim after every transition.

When To Use Or Avoid Union-Find

Use It When

  • Use Union-Find when this precondition is stated or can be proved: Connectivity can be represented by stable element identities and component merges.
  • Use it when this maintained state removes repeated work: Each element reaches exactly one representative for its component.

Choose Another Tool When

  • Avoid Union-Find when this precondition is absent: Connectivity can be represented by stable element identities and component merges.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: Connectivity can be represented by stable element identities and component merges.

Avoid

def component_count(node_count, edges):
    pass

Use instead

def component_count(node_count, edges):
    parent = list(range(node_count))
    size = [1] * node_count
    def find(node):
        while node != parent[node]:
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node
    count = node_count
    for left, right in edges:
        a, b = find(left), find(right)
        if a == b:
            continue
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
        count -= 1
    return count

Where you will hit this: Count Components with Union-Find(opens in a new tab)

Breaking the state transition

Decrements for every edge, including edges within one component.

Prevent it: Preserve this proof obligation: Parent links preserve equivalence classes, while compression and balancing change representation but not membership.

Avoid

def component_count(n,edges):
    return n-len(edges)

Use instead

def component_count(node_count, edges):
    parent = list(range(node_count))
    size = [1] * node_count
    def find(node):
        while node != parent[node]:
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node
    count = node_count
    for left, right in edges:
        a, b = find(left), find(right)
        if a == b:
            continue
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
        count -= 1
    return count

Where you will hit this: Count Components with Union-Find(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O((n + e) alpha(n)).

Avoid

def component_count(n,edges):
    return n-len(edges)

Use instead

def component_count(node_count, edges):
    parent = list(range(node_count))
    size = [1] * node_count
    def find(node):
        while node != parent[node]:
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node
    count = node_count
    for left, right in edges:
        a, b = find(left), find(right)
        if a == b:
            continue
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
        count -= 1
    return count

Where you will hit this: Lowest Common Ancestor in a BST(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.