Get started

Union Find Coding Problems: 33 Questions with Solutions

33 union find coding problems — 1 easy · 26 medium · 6 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 7-day plan.

  • Problems: 33
  • By difficulty: 1 easy · 26 medium · 6 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

A disjoint-set structure answers "are these two in the same group?" and merges groups in near-constant time. Counting components as edges arrive, detecting the edge that closes a cycle, and grouping accounts or islands by shared links are its uses; the problems here practise the find-with-path-compression and union-by-size that keep it fast.

How union find works, step by step

012345parent000102030405size6·····connected(5, 1) = true; all in one set
Merging sets and answering connected? queries, with union-find. Example: n = 6; union(0, 1), union(2, 3), union(4, 5), union(1, 3), connected(3, 5), union(3, 5), connected(5, 1)
  1. Union-find keeps disjoint sets as trees: parent[i] points one step towards the set's root, and a root points at itself. At the start each of the 6 elements is its own set of size 1.
  2. union(0, 1): find(0) = 0 and find(1) = 1 are both roots. Sizes 1 and 1 tie, and a tie goes to the first root, so root 1 goes under 0: parent[1] = 0, size[0] = 2. Each root keeps its set's size so the next union knows which tree is bigger.
  3. union(2, 3) and union(4, 5) follow the same rule: each joins two single elements, so parent[3] = 2 and parent[5] = 4. That leaves 3 sets: {0, 1}, {2, 3} and {4, 5}.
  4. union(1, 3): find(1) walks 1 → 0 and find(3) walks 3 → 2. Sizes 2 and 2 tie again, so root 2 goes under 0: parent[2] = 0, size[0] = 4. A node sinks a level only when its tree is hung under one at least as big, so its set at least doubles each time: no node sinks more than log₂ n levels.
  5. connected(3, 5)? find(3) walks 3 → 2 → 0 and find(5) walks 5 → 4. On the way back, path compression points 3 straight at the root: parent[3] = 0. The roots are 0 and 4, so no.
  6. union(3, 5): find(3) now takes one hop, 3 → 0, thanks to the compression; find(5) walks 5 → 4. Size 4 beats size 2, so root 4 goes under 0: parent[4] = 0, size[0] = 6. Hanging the smaller tree under the larger leaves the bigger tree's depths alone: only 4 and 5 sink one level.
  7. connected(5, 1)? find(5) walks 5 → 4 → 0 and find(1) walks 1 → 0. On the way back, path compression points 5 straight at the root: parent[5] = 0. The roots are both 0, so yes, they are in one set.
  8. So connected(5, 1) = true. Every element now points straight at root 0, so any later find is one hop. With union by size and path compression, m operations cost O(m·α(n)), where α stays below 5 for any real n.

Union Find study plan

11 of the 33 Union Find problems (1 easy, 7 medium and 3 hard) over 7 days, about 7 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 22 in the full list below are practice at your own pace. Then move on to Shortest Path.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.

Day 2

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 5

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Day 6

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Shortest Path

Union Find: the essentials

When to reach for it

Connectivity that only grows: edges are added and never removed, and the questions are "are these two connected?", "how many groups are there?", "which edge first joins two nodes that were already connected?". It also fits offline problems — sort edges or queries by weight and union as the threshold rises, as in Kruskal's minimum spanning tree. It cannot split a group, and it gives neither paths nor distances.

The pattern

Every node points to a parent; a root points to itself and names its group. find follows parents to the root, shortening the path as it goes; union hangs the smaller tree's root under the larger one's.

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

def union(parent, size, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra == rb: return False           # already joined: this edge closes a cycle
    if size[ra] < size[rb]: ra, rb = rb, ra
    parent[rb], size[ra] = ra, size[ra] + size[rb]
    return True

Cost

With path compression (or halving) and union by size, m operations take O(m α(n)), where α, the inverse Ackermann function, is at most 4 for any input that fits in memory. Space is O(n). Without either, a chain can form and each find degrades to O(n).

Common mistakes

  • Comparing parent[a] == parent[b] instead of find(a) == find(b).
  • Counting groups as the distinct values in parent without calling find on each node first.
  • Decrementing the component count on every union call, rather than only when two different roots merge.
  • Mapping non-integer keys (emails, coordinates) to indices inconsistently.

Start with

All union find problems

Easy (1)

Medium (26)

Hard (6)

Companies that ask union find problems

Next topic: Shortest Path