Data Structure1 Practice2 Interview

Disjoint Set Union

GuideCode Labs

Partition structure supporting near-constant-time connectivity queries through find and union. This guide turns that contract into deliberate Python operations, interview invariants, and a runnable practice loop.

Recognize it when

Consider Disjoint Set Union when the prompt's constraints and required operations match this shape: Partition structure supporting near-constant-time connectivity queries through find and union.

On this page · Mental Model

Checking your account…

Mental Model

Disjoint Set Union maintains a partition of nodes into non-overlapping components. Each component is represented by one root; two nodes are connected exactly when find returns the same root.

Represent Components by Roots

Initially every node is its own parent. Only roots may become children during union. Parent pointers encode membership, while root size or rank guides which representative remains.

Compress Find Paths

find follows parents to a root, then rewrites visited parents toward that root. Compression changes shape but never component membership.

Compress Parent Paths

Reference

def compress_all(parent):
    compressed = parent.copy()
    def find(node):
        if compressed[node] != node:
            compressed[node] = find(compressed[node])
        return compressed[node]
    roots = [find(node) for node in range(len(compressed))]
    return roots, compressed

Practice

Implement compress_all(parent). Return roots for every node and a copied parent array compressed directly to roots.

def compress_all(parent):
    return parent.copy(), parent.copy()

Public tests

Verify roots and compressed parents

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

Union by Size

Attach the smaller root below the larger and update size only at the surviving root. With path compression, a sequence of operations has inverse-Ackermann amortized time, effectively constant for interview-scale inputs.

Trace Union Connectivity

Reference

def disjoint_set_trace(node_count, operations):
    parent = list(range(node_count))
    size = [1] * node_count
    def find(node):
        while parent[node] != node:
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node
    results = []
    for operation, left, right in operations:
        left_root, right_root = find(left), find(right)
        if operation == 'connected':
            results.append(left_root == right_root)
        elif left_root != right_root:
            if size[left_root] < size[right_root]:
                left_root, right_root = right_root, left_root
            parent[right_root] = left_root
            size[left_root] += size[right_root]
    return results

Practice

Implement disjoint_set_trace(node_count, operations) with union by size and path compression; return connected-query booleans.

def disjoint_set_trace(node_count, operations):
    return [False for operation in operations if operation[0] == 'connected']

Public tests

Verify component connectivity

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

Choose DSU or Graph Traversal

Choose DSU for incremental undirected connectivity, cycle checks while adding edges, or Kruskal. Choose DFS/BFS when actual paths, distances, directed reachability, or component contents are needed.

Common Pitfalls

Attaching arbitrary nodes instead of roots corrupts the partition.
Updating size on a non-root makes union decisions stale.
DSU cannot remove edges or explain the connecting path without additional machinery.
Calling the bound worst-case O(1) overstates the amortized guarantee.

Explain It in an Interview

Define root identity, then separate correctness (same root means same component) from optimizations (compression and size). State amortized complexity across the complete operation sequence.

Trace Disjoint-Set Connectivity(opens in a new tab) isolates operations; Number of Islands(opens in a new tab) is usually simpler with traversal unless cells arrive dynamically.

Python Version Note

Python 3.11+

The examples use standard Python containers and syntax available in the supported browser runtime; Disjoint Set Union itself is taught as an interview abstraction.

Verify in Python docs

Complexity & Invariants

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

Operation	Average	Worst	Interview note
Core Disjoint Set Union workflow	`O((n + m) alpha(n))`	`O((n + m) alpha(n))`	Maintain parent and component-size arrays, find compressed roots, and attach the smaller root to the larger.

Space

O(n) for the demonstrated Disjoint Set Union workflow.

Assumptions

State the concrete operation and representation before claiming a bound; tree height and graph density can change it.
The bound counts the operations in Trace Disjoint-Set Connectivity and does not hide Python slicing, sorting, or copying.

Invariants Worth Saying Aloud

State the precise Disjoint Set Union invariant before coding and preserve it after every update, traversal step, or recursive return.
Represent each component by one root. This remains true after every accepted operation.
Combine path compression with union by size without corrupting component identity. This remains true after every accepted operation.

When To Use Or Avoid Disjoint Set Union

Use It When

Use Disjoint Set Union when its representation directly supports the prompt's repeated query or update.
Use it when the invariant can be stated before coding and preserved after every operation.

Choose Another Tool When

Avoid it when a simpler Python sequence or mapping communicates the same contract with less state.
Avoid it when building the structure costs more time or space than the number of required queries can justify.

Common Pitfalls

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

Leaving the core transition unfinished

Placeholder code cannot preserve the Disjoint Set Union invariant or satisfy the public contract.

Prevent it: Implement the smallest complete transition and run the public tests before adding optimizations.

Avoid

def disjoint_set_trace(node_count, operations):
    pass

Use instead

def disjoint_set_trace(node_count, operations):
    parent = list(range(node_count))
    size = [1] * node_count
    results = []
    def find(node):
        while parent[node] != node:
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node
    for operation, left, right in operations:
        if operation == "union":
            left_root, right_root = find(left), find(right)
            if left_root == right_root:
                continue
            if size[left_root] < size[right_root]:
                left_root, right_root = right_root, left_root
            parent[right_root] = left_root
            size[left_root] += size[right_root]
        elif operation == "connected":
            results.append(find(left) == find(right))
    return results

Where you will hit this: Trace Disjoint-Set Connectivity(opens in a new tab)

Breaking the central invariant

Compares immediate parent entries rather than roots, so transitive connectivity queries can return false.

Prevent it: Keep this invariant visible while editing: State the precise Disjoint Set Union invariant before coding and preserve it after every update, traversal step, or recursive return.

Avoid

def disjoint_set_trace(node_count, operations):
    parent = list(range(node_count))
    results = []
    for operation, left, right in operations:
        if operation == "union":
            parent[right] = left
        else:
            results.append(parent[left] == parent[right])
    return results

Use instead

def disjoint_set_trace(node_count, operations):
    parent = list(range(node_count))
    size = [1] * node_count
    results = []
    def find(node):
        while parent[node] != node:
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node
    for operation, left, right in operations:
        if operation == "union":
            left_root, right_root = find(left), find(right)
            if left_root == right_root:
                continue
            if size[left_root] < size[right_root]:
                left_root, right_root = right_root, left_root
            parent[right_root] = left_root
            size[left_root] += size[right_root]
        elif operation == "connected":
            results.append(find(left) == find(right))
    return results

Where you will hit this: Trace Disjoint-Set Connectivity(opens in a new tab)

Hiding Python work inside the loop

Handle empty state, duplicate values, aliasing, and serialization boundaries explicitly in tests.

Prevent it: Account for every slice, copy, sort, membership test, and container mutation before claiming O((n + m) alpha(n)).

Avoid

def disjoint_set_trace(node_count, operations):
    parent = list(range(node_count))
    results = []
    for operation, left, right in operations:
        if operation == "union":
            parent[right] = left
        else:
            results.append(parent[left] == parent[right])
    return results

Use instead

def disjoint_set_trace(node_count, operations):
    parent = list(range(node_count))
    size = [1] * node_count
    results = []
    def find(node):
        while parent[node] != node:
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node
    for operation, left, right in operations:
        if operation == "union":
            left_root, right_root = find(left), find(right)
            if left_root == right_root:
                continue
            if size[left_root] < size[right_root]:
                left_root, right_root = right_root, left_root
            parent[right_root] = left_root
            size[left_root] += size[right_root]
        elif operation == "connected":
            results.append(find(left) == find(right))
    return results

Where you will hit this: Number of Islands(opens in a new tab)

Reviewed References

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

Python More on Lists(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…