-
Notifications
You must be signed in to change notification settings - Fork 0
021 — Union Find Pattern
The Union-Find chapter covered the data structure itself — find, union, path compression, union by rank. This chapter is about recognizing when to reach for it: the family of problems where you're not given a graph up front, but you're given a stream of pairwise relationships and asked a question about the groups those relationships form.
Picture a wave of small-town mergers. Every so often, two neighboring villages agree to merge into a single township, adopting one shared town hall. Over months, hundreds of these merges happen in essentially random order — village 3 merges with village 7, then later the township containing village 7 merges with the one containing village 12, and so on. At any moment, someone might ask: "are villages 3 and 12 currently part of the same township?" You don't want to redraw the entire map of mergers from scratch to answer that — you just want to trace each village up to its township's current town hall and compare. That's the whole pattern: relationships arrive one pair at a time, groups grow by merging, and the recurring question is always some version of "are these two in the same group now?" or "how many groups are left?"
The Union-Find pattern is a strong reach when you see:
- "Connected components" or "number of provinces/islands/groups" — counting how many separate clusters exist after a series of pairwise connections, without needing to enumerate each cluster's full membership.
- A stream of pairs given one at a time, combined with a question like "are these two connected?" or "at what point do they become connected?" — e.g. "given a sequence of friend requests, at which request does everyone become connected in one group?" Processing edges one at a time and repeatedly querying connectivity is the signature this data structure was built for, since it beats re-running BFS/DFS after every new edge.
-
Cycle detection in an undirected graph while building it edge-by-edge — "redundant connection: find the edge that, if removed, turns the graph back into a tree" — a cycle exists exactly when
union(a, b)is called on two nodes already in the same group. - Grid problems phrased as "merge adjacent same-valued cells into groups" — "number of islands," "accounts merge" (merging accounts that share an email) — anywhere the relationship (adjacency, shared attribute) is the thing driving which items belong together, more so than any tree/graph structure being handed to you directly.
The unifying tell: relationships are discovered incrementally (edge by edge, pair by pair) rather than given as a complete static graph, and the recurring question is about group membership, not about paths or distances within a group.
Counting connected components as edges arrive one at a time — watch the group count drop only when a merge actually happens:
6 elements, no edges yet: {0} {1} {2} {3} {4} {5} groups = 6
edge (0,1): union(0,1) → {0,1} {2} {3} {4} {5} groups = 5
edge (2,3): union(2,3) → {0,1} {2,3} {4} {5} groups = 4
edge (1,2): union(1,2) → {0,1,2,3} {4} {5} groups = 3
(1 and 2's ROOTS merge — the entire
{0,1} group joins the entire {2,3} group)
edge (0,3): union(0,3) → find(0) == find(3) already!
NO merge happens — groups stays 3
(this edge is redundant — it closes a cycle)
Final: {0,1,2,3} {4} {5} → 3 connected components
final class UnionFindPattern {
private var parent: [Int]
private var rank: [Int]
private(set) var groupCount: Int
init(size: Int) {
parent = Array(0..<size)
rank = Array(repeating: 0, count: size)
groupCount = size
}
func find(_ x: Int) -> Int {
if parent[x] != x {
parent[x] = find(parent[x]) // path compression
}
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 connected — this IS a cycle/redundant edge
if rank[rootA] < rank[rootB] {
parent[rootA] = rootB
} else if rank[rootA] > rank[rootB] {
parent[rootB] = rootA
} else {
parent[rootB] = rootA
rank[rootA] += 1
}
groupCount -= 1
return true
}
}
func unionFindPatternTemplate(size: Int, pairs: [(Int, Int)]) -> Int {
let uf = UnionFindPattern(size: size)
for (a, b) in pairs {
uf.union(a, b) // 🔧 Fill in: react to the return value if you need to know
// WHICH edge was redundant, not just the final group count.
}
return uf.groupCount // 🔧 Fill in: return whatever the problem actually asks for.
}The skeleton never changes from the Union-Find chapter's implementation — this chapter is entirely about the driver loop around it: initialize one element per item, feed in relationships one at a time via union, and either read off groupCount at the end or inspect union's boolean return value the moment a redundant/cycle-forming edge shows up.
Number of Provinces — given an n x n adjacency matrix isConnected where isConnected[i][j] == 1 means city i and city j are directly connected, return the total number of provinces (a province is a group of directly or indirectly connected cities).
func findCircleNum(_ isConnected: [[Int]]) -> Int {
let n = isConnected.count
let uf = UnionFindPattern(size: n)
for i in 0..<n {
for j in (i + 1)..<n {
if isConnected[i][j] == 1 {
uf.union(i, j)
}
}
}
return uf.groupCount
}
// smoke test
print(findCircleNum([[1,1,0],[1,1,0],[0,0,1]])) // 2
print(findCircleNum([[1,0,0],[0,1,0],[0,0,1]])) // 3
print(findCircleNum([[1,1,1],[1,1,1],[1,1,1]])) // 1Mapped onto the template: pairs isn't handed to us as an explicit list — it's implicit in the adjacency matrix, so the nested loop over i, j plays the role of "feed relationships in one at a time." Every isConnected[i][j] == 1 becomes a union(i, j) call, exactly like the template's loop body. The answer needed is just the final group count, so uf.groupCount is returned directly — no need to inspect union's return value here, since we don't care which edges were redundant, only how many groups remain.
The Union-Find pattern is a wave of village mergers — relationships arrive one pair at a time, and "are these two in the same township now?" is answered by tracing up to the town hall, never by redrawing the whole map.
A problem gives you a list of accounts, each with a name and a list of emails, and says two accounts belong to the same person if they share at least one email — merge accounts belonging to the same person. Explain what would play the role of "element" in your Union-Find setup (it's not obviously an integer index like in the worked example above), and how you'd turn "shares an email" into a union call.