Skip to content

012 — Union Find

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

12 — Union-Find

Graphs (last chapter) can answer "is there a path from A to B" with a BFS or DFS — but that's a full traversal every single time you ask. Union-Find answers a narrower question — "are A and B in the same connected group" — and answers it in almost constant time, even after thousands of groups have merged together.

🍽️ Intuition

Picture a school with hundreds of students who keep forming and merging friend groups. Every so often, two groups discover they actually know each other and merge into one bigger group. Someone asks you constantly: "are Alex and Jordan in the same friend group?"

You could re-trace every friendship chain from scratch each time — slow, and it gets slower as groups merge into bigger ones. Or: every friend group elects one representative. To check if two people are in the same group, you just ask each of them "who's your group's representative?" — if it's the same person, they're in the same group. Merging two groups is just as cheap: one representative now points to the other.

  • 👥 Each group has exactly one representative (the "root").
  • 🔎 find(person) — chase pointers up until you reach the representative.
  • 🤝 union(personA, personB) — merge their two groups by pointing one representative at the other.

That's the entire idea. No traversal of the whole group needed — just a pointer chase to the top.

🧠 What It Is & When To Reach For It

Union-Find (also called a Disjoint Set Union, or DSU) tracks a collection of elements partitioned into non-overlapping ("disjoint") groups, and supports two operations efficiently:

  • find(x) — which group does x belong to? (Returns that group's representative/root.)
  • union(x, y) — merge the groups containing x and y into one.

The naive version — each element stores a pointer to its parent, find walks up to the root — works, but a long chain of unions can degrade into an O(n)-deep chain, making find slow. Two independent optimizations fix that, and interviews usually expect both:

  • Path compression — while find walks up to the root, it rewires every node it passed through to point directly at the root. Future find calls on those nodes become instant.
  • Union by rank (or size) — when merging two groups, always attach the shorter tree under the taller one's root, instead of arbitrarily. This keeps trees flat instead of accidentally building a long chain.

Together, these two tricks give amortized O(α(n)) per operation — α is the inverse Ackermann function, which grows so slowly that for any n you could realistically store in memory, α(n) ≤ 4. In practice: treat Union-Find operations as constant time.

Swift has no stdlib Union-Find — hand-rolled as a class wrapping a parent array and a rank array, indexed by integer.

Reach for Union-Find when:

  • You need to repeatedly answer "are these two things connected" as connections keep getting added — Union-Find beats re-running BFS/DFS from scratch every time.
  • You're detecting cycles in an undirected graph while building it edge by edge — a cycle exists exactly when union(a, b) is called on two nodes that are already in the same group.
  • Classic use cases: Kruskal's minimum spanning tree algorithm, counting connected components, "number of provinces/islands"-style grouping problems, checking if a graph stays fully connected as edges are removed.

Skip it when the graph structure is fixed and you only need to check connectivity once or twice — a single BFS/DFS is simpler and just as fast for a one-off query.

📊 ASCII Diagram

Starting with 6 separate elements (each its own group), after union(0,1), union(1,2), union(3,4):

Before any union — 6 separate groups, each element is its own root:
  0   1   2   3   4   5
  │   │   │   │   │   │
  0   1   2   3   4   5   (parent[i] == i for all i)

After union(0,1), union(1,2), union(3,4):

        0            3          5
       / \           |          |
      1   (rank 1)   4          5   (still alone)
      |
      2

  parent: [0, 0, 1, 3, 3, 5]
              ↑ 2's parent is 1, but find(2) walks 2 → 1 → 0

After find(2) runs once (path compression kicks in):

        0
      / | \
     1  2  (rank still 1 — compression doesn't touch rank)
     
  parent: [0, 0, 0, 3, 3, 5]
              ↑ 2 now points DIRECTLY at 0 — future find(2) is instant

💻 Swift Implementation

No stdlib equivalent — hand-rolled over Int indices (the standard interview form; wrap with a [T: Int] lookup if you need arbitrary hashable elements).

final class UnionFind {
    private var parent: [Int]
    private var rank: [Int]
    private(set) var groupCount: Int

    init(size: Int) {
        parent = Array(0..<size)              // everyone starts as their own representative
        rank = Array(repeating: 0, count: size)
        groupCount = size
    }

    func find(_ x: Int) -> Int {
        if parent[x] != x {
            parent[x] = find(parent[x])   // path compression: flatten the chain on the way up
        }
        return parent[x]
    }

    @discardableResult
    func union(_ a: Int, _ b: Int) -> Bool {
        let rootA = find(a)
        let rootB = find(b)
        guard rootA != rootB else { return false }   // already in the same group — this IS a cycle

        // union by rank: attach the shorter tree under the taller one's root
        if rank[rootA] < rank[rootB] {
            parent[rootA] = rootB
        } else if rank[rootA] > rank[rootB] {
            parent[rootB] = rootA
        } else {
            parent[rootB] = rootA
            rank[rootA] += 1   // trees were equal height — new tree is one taller
        }
        groupCount -= 1
        return true
    }

    func connected(_ a: Int, _ b: Int) -> Bool {
        find(a) == find(b)
    }
}

Usage:

let uf = UnionFind(size: 6)
uf.union(0, 1)
uf.union(1, 2)
uf.union(3, 4)

uf.connected(0, 2)   // true  — 0 and 2 both trace back to the same root
uf.connected(0, 3)   // false — never merged
uf.groupCount        // 3 — groups are {0,1,2}, {3,4}, {5}

The union function's return value doubles as a cycle detector: if union(a, b) returns false, a and b were already connected before this call — adding an edge between them would create a cycle.

⏱️ Core Operations & Big-O

Operation Big-O Why
find (with path compression) O(α(n)) amortized Each call flattens the chain it walks — so future calls on those same nodes are near-instant. α(n) is the inverse Ackermann function; for all practical n, treat this as O(1). See Big-O Notation.
union (with union by rank) O(α(n)) amortized Dominated by two find calls, plus O(1) pointer rewiring — union by rank keeps tree height from ever growing unboundedly.
connected O(α(n)) amortized Just two find calls compared for equality.
find with no optimizations O(n) worst case A naive union that always attaches arbitrarily can build a straight-line chain n deep — find degenerates into a linked-list walk.
Space O(n) Two arrays (parent, rank), each sized to the number of elements.

🧸 Memory Sentence

Union-Find is friend groups with elected representatives — asking "same group?" is just "same rep?", and merging two groups is just pointing one rep at the other, with path compression flattening the chain every time you ask.

✅ Check Your Understanding

Suppose you implement union without union by rank — always attaching find(b)'s root under find(a)'s root, regardless of tree height. Construct a sequence of union calls on elements 0 through 4 that produces the worst possible shape (a straight chain of depth 5). Then explain how path compression alone (still no union by rank) would affect the cost of a second find call on the deepest node, versus the first.

⬅️ Previous: Graphs · Next: Segment & Fenwick Trees ➡️

Clone this wiki locally