Union-Find (Disjoint Set Union) Interview Questions
Last updated 2026-11-19
Union-find, also called disjoint set union or DSU, tracks a collection of groups and answers two questions fast: which group is this element in, and merge these two groups. With path compression and union by size each operation costs close to constant time, which makes it ideal when connections arrive one at a time.
The problems below begin with the data structure itself and move to accounts merge and online island counting. Each has Python and Java code, complexity and edge cases. For the traversal-based alternatives see graph interview questions; for the main algorithm built on DSU see minimum spanning tree interview questions.
| find / union | O(alpha(n)) amortised |
|---|---|
| Optimisations | Path compression, union by size or rank |
| Best for | Dynamic connectivity, cycle detection in undirected graphs |
| Not for | Directed reachability or deleting edges |
The pattern and when to spot it
Spot DSU when a problem keeps merging things into groups and asks whether two items are connected, how many groups remain, or which edge makes a cycle. Edges that arrive in a stream or equations such as a equals b are strong hints, because a traversal would need to be redone after every change while DSU just merges two roots.
Almost every DSU solution is the same skeleton: create sets, union pairs, then read a count, a size or a representative. Map non-integer items to indices first, or use a dictionary-based parent map. Use the return value of union to count components, since it is False exactly when the two items were already together.
Things worth knowing
- Without optimisations a chain of unions can build a tree of height n, making find O(n).
- Path halving, p[x] = p[p[x]], is a short iterative form of path compression and avoids recursion limits.
- DSU cannot undo unions, so problems with deletions need offline processing in reverse or a different structure.
- Directed graphs need strongly connected components or topological sort, not DSU.
- Size the parent array correctly for 1-indexed vertices.
Union-Find (Disjoint Set Union) Interview Questions: questions with worked answers
1 Implement union-find with path compression and union by size
easyKeep a parent array where each root points to itself. find follows parents to the root and shortens the path as it goes (path halving). union joins the smaller tree under the larger and returns False if the two were already together. Together the two optimisations make each operation almost constant time, specifically O(alpha(n)). Time O(alpha(n)) amortised per operation, space O(n). Edge cases: union of an element with itself, repeated unions of the same pair, out-of-range indices.
pythonclass DSU: def __init__(self, n): self.p = list(range(n)) self.sz = [1] * n def find(self, x): while self.p[x] != x: self.p[x] = self.p[self.p[x]] x = self.p[x] return x def union(self, a, b): a, b = self.find(a), self.find(b) if a == b: return False if self.sz[a] < self.sz[b]: a, b = b, a self.p[b] = a self.sz[a] += self.sz[b] return Truejavaclass DSU { int[] p, sz; DSU(int n) { p = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) { int t = a; a = b; b = t; } p[b] = a; sz[a] += sz[b]; return true; } }2 Number of provinces (connected components)
easyStart with n components. For every pair connected in the matrix, call union and decrement the count whenever a union actually merged two different sets. The final count is the answer. This is the DSU version of the DFS solution. Time O(n^2 * alpha(n)), space O(n). Edge cases: only the diagonal set (n provinces), full matrix (1 province), checking only the upper triangle to halve the work.
pythonclass DSU: def __init__(self, n): self.p = list(range(n)) self.sz = [1] * n def find(self, x): while self.p[x] != x: self.p[x] = self.p[self.p[x]] x = self.p[x] return x def union(self, a, b): a, b = self.find(a), self.find(b) if a == b: return False if self.sz[a] < self.sz[b]: a, b = b, a self.p[b] = a self.sz[a] += self.sz[b] return True def find_circle_num(m): n = len(m) d = DSU(n) count = n for i in range(n): for j in range(i + 1, n): if m[i][j] and d.union(i, j): count -= 1 return countjavaclass DSU { int[] p, sz; DSU(int n) { p = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) { int t = a; a = b; b = t; } p[b] = a; sz[a] += sz[b]; return true; } } int findCircleNum(int[][] m) { int n = m.length, count = n; DSU d = new DSU(n); for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (m[i][j] == 1 && d.union(i, j)) count--; return count; }3 Redundant connection: the edge that closes a cycle
mediumAdd the edges in order. The first edge whose endpoints are already in the same set is the one that creates the cycle, so it is the redundant edge. If several answers exist the problem usually asks for the one that appears last in the input; process in order and return the last failing edge. Time O(n * alpha(n)), space O(n). Edge cases: one-based vertex labels (size the array n + 1), the cycle edge being the very last one, the graph being a tree plus exactly one extra edge.
pythonclass DSU: def __init__(self, n): self.p = list(range(n)) self.sz = [1] * n def find(self, x): while self.p[x] != x: self.p[x] = self.p[self.p[x]] x = self.p[x] return x def union(self, a, b): a, b = self.find(a), self.find(b) if a == b: return False if self.sz[a] < self.sz[b]: a, b = b, a self.p[b] = a self.sz[a] += self.sz[b] return True def redundant(edges): d = DSU(len(edges) + 1) ans = None for a, b in edges: if not d.union(a, b): ans = [a, b] return ansjavaclass DSU { int[] p, sz; DSU(int n) { p = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) { int t = a; a = b; b = t; } p[b] = a; sz[a] += sz[b]; return true; } } int[] redundant(int[][] edges) { DSU d = new DSU(edges.length + 1); int[] ans = null; for (int[] e : edges) if (!d.union(e[0], e[1])) ans = e; return ans; }4 Is the graph a valid tree?
mediumA graph is a tree when it has exactly n-1 edges and no edge joins two vertices that are already connected. Union each edge and fail on the first one that returns False, then check the edge count. Time O(n * alpha(n)), space O(n). Edge cases: n equal to 1 with no edges, n-1 edges but a cycle and a separate component, edge count not equal to n-1.
pythonclass DSU: def __init__(self, n): self.p = list(range(n)) self.sz = [1] * n def find(self, x): while self.p[x] != x: self.p[x] = self.p[self.p[x]] x = self.p[x] return x def union(self, a, b): a, b = self.find(a), self.find(b) if a == b: return False if self.sz[a] < self.sz[b]: a, b = b, a self.p[b] = a self.sz[a] += self.sz[b] return True def valid_tree(n, edges): if len(edges) != n - 1: return False d = DSU(n) return all(d.union(a, b) for a, b in edges)javaclass DSU { int[] p, sz; DSU(int n) { p = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) { int t = a; a = b; b = t; } p[b] = a; sz[a] += sz[b]; return true; } } boolean validTree(int n, int[][] edges) { if (edges.length != n - 1) return false; DSU d = new DSU(n); for (int[] e : edges) if (!d.union(e[0], e[1])) return false; return true; }5 Satisfiability of equality equations
mediumProcess all equations of the form a==b first and union them. Then check each a!=b: if both sides lie in the same set the system is contradictory. Handle the two kinds in two passes because order matters. Time O(n * alpha(26)), space O(26). Edge cases: a!=a (always false), only inequalities (true unless a!=a), chains such as a==b, b==c, a!=c.
pythondef equations_possible(eqs): p = list(range(26)) def find(x): while p[x] != x: p[x] = p[p[x]] x = p[x] return x for e in eqs: if e[1] == '=': p[find(ord(e[0]) - 97)] = find(ord(e[3]) - 97) for e in eqs: if e[1] == '!' and find(ord(e[0]) - 97) == find(ord(e[3]) - 97): return False return Truejavaboolean equationsPossible(String[] eqs) { DSU d = new DSU(26); for (String e : eqs) if (e.charAt(1) == '=') d.union(e.charAt(0) - 'a', e.charAt(3) - 'a'); for (String e : eqs) if (e.charAt(1) == '!' && d.find(e.charAt(0) - 'a') == d.find(e.charAt(3) - 'a')) return false; return true; } class DSU { int[] p, sz; DSU(int n) { p = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) { int t = a; a = b; b = t; } p[b] = a; sz[a] += sz[b]; return true; } }6 Most stones removed in a grid
mediumA stone can be removed if another stone shares its row or column. In each connected group of such stones all but one can be removed. Union each stone row with its column (offset the column ids), count the number of groups, and the answer is stones minus groups. Time O(n * alpha), space O(n). Edge cases: a single stone (0 removals), stones all in one row, no two stones sharing a line, coordinates up to 10^4.
pythondef remove_stones(stones): p = {} def find(x): p.setdefault(x, x) while p[x] != x: p[x] = p[p[x]] x = p[x] return x for r, c in stones: p[find(r)] = find(~c) # ~c keeps columns apart from rows return len(stones) - len({find(x) for x in list(p)})javaint removeStones(int[][] stones) { Map<Integer, Integer> p = new HashMap<>(); for (int[] s : stones) union(p, s[0], ~s[1]); Set<Integer> roots = new HashSet<>(); for (int x : new ArrayList<>(p.keySet())) roots.add(find(p, x)); return stones.length - roots.size(); } private int find(Map<Integer, Integer> p, int x) { p.putIfAbsent(x, x); while (p.get(x) != x) { p.put(x, p.get(p.get(x))); x = p.get(x); } return x; } private void union(Map<Integer, Integer> p, int a, int b) { p.put(find(p, a), find(p, b)); }7 Longest consecutive sequence using union-find
mediumFor each number x, union it with x-1 and x+1 when those exist in the set. The size of the largest component is the answer. The set-based scan from sequence starts is simpler, but this shows the DSU alternative with a map from value to index. Time O(n * alpha(n)), space O(n). Edge cases: duplicates (skip repeats so they are not counted twice), empty array (0), negative numbers.
pythonclass DSU: def __init__(self, n): self.p = list(range(n)) self.sz = [1] * n def find(self, x): while self.p[x] != x: self.p[x] = self.p[self.p[x]] x = self.p[x] return x def union(self, a, b): a, b = self.find(a), self.find(b) if a == b: return False if self.sz[a] < self.sz[b]: a, b = b, a self.p[b] = a self.sz[a] += self.sz[b] return True def longest_consecutive(nums): idx = {} for x in nums: idx.setdefault(x, len(idx)) d = DSU(len(idx)) for x in idx: if x + 1 in idx: d.union(idx[x], idx[x + 1]) return max((d.sz[d.find(i)] for i in range(len(idx))), default=0)javaclass DSU { int[] p, sz; DSU(int n) { p = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) { int t = a; a = b; b = t; } p[b] = a; sz[a] += sz[b]; return true; } } int longestConsecutive(int[] nums) { Map<Integer, Integer> idx = new HashMap<>(); for (int x : nums) idx.putIfAbsent(x, idx.size()); DSU d = new DSU(idx.size()); for (int x : idx.keySet()) if (idx.containsKey(x + 1)) d.union(idx.get(x), idx.get(x + 1)); int best = 0; for (int i = 0; i < idx.size(); i++) best = Math.max(best, d.sz[d.find(i)]); return best; }8 Smallest string after swaps at allowed index pairs
mediumIndices linked by swap pairs, directly or through others, can be rearranged freely within their component. Union the pairs, collect the characters of each component, sort them, and write them back into the component positions in sorted order. Time O(n log n), space O(n). Edge cases: no pairs (string unchanged), a single component (fully sorted string), repeated pairs.
pythonclass DSU: def __init__(self, n): self.p = list(range(n)) self.sz = [1] * n def find(self, x): while self.p[x] != x: self.p[x] = self.p[self.p[x]] x = self.p[x] return x def union(self, a, b): a, b = self.find(a), self.find(b) if a == b: return False if self.sz[a] < self.sz[b]: a, b = b, a self.p[b] = a self.sz[a] += self.sz[b] return True from collections import defaultdict def smallest_string(s, pairs): d = DSU(len(s)) for a, b in pairs: d.union(a, b) groups = defaultdict(list) for i in range(len(s)): groups[d.find(i)].append(i) res = list(s) for idxs in groups.values(): chars = sorted(res[i] for i in idxs) for i, ch in zip(idxs, chars): res[i] = ch return ''.join(res)javaclass DSU { int[] p, sz; DSU(int n) { p = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) { int t = a; a = b; b = t; } p[b] = a; sz[a] += sz[b]; return true; } } String smallestString(String s, List<List<Integer>> pairs) { DSU d = new DSU(s.length()); for (List<Integer> p : pairs) d.union(p.get(0), p.get(1)); Map<Integer, List<Integer>> groups = new HashMap<>(); for (int i = 0; i < s.length(); i++) groups.computeIfAbsent(d.find(i), k -> new ArrayList<>()).add(i); char[] res = s.toCharArray(); for (List<Integer> idxs : groups.values()) { char[] cs = new char[idxs.size()]; for (int k = 0; k < cs.length; k++) cs[k] = s.charAt(idxs.get(k)); Arrays.sort(cs); for (int k = 0; k < cs.length; k++) res[idxs.get(k)] = cs[k]; } return new String(res); }9 Accounts merge: group emails belonging to the same person
hardTwo accounts belong to the same person if they share any email. Map each email to the first account index that used it and union the account indices when an email repeats. Group emails by root, sort each group and prepend the account name. Time O(N log N) for N emails, space O(N). Edge cases: same name for different people (do not merge by name), an email appearing in many accounts, a single account.
pythonclass DSU: def __init__(self, n): self.p = list(range(n)) self.sz = [1] * n def find(self, x): while self.p[x] != x: self.p[x] = self.p[self.p[x]] x = self.p[x] return x def union(self, a, b): a, b = self.find(a), self.find(b) if a == b: return False if self.sz[a] < self.sz[b]: a, b = b, a self.p[b] = a self.sz[a] += self.sz[b] return True from collections import defaultdict def accounts_merge(accounts): d = DSU(len(accounts)) owner = {} for i, acc in enumerate(accounts): for e in acc[1:]: if e in owner: d.union(owner[e], i) else: owner[e] = i groups = defaultdict(list) for e, i in owner.items(): groups[d.find(i)].append(e) return [[accounts[r][0]] + sorted(es) for r, es in groups.items()]javaclass DSU { int[] p, sz; DSU(int n) { p = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) { int t = a; a = b; b = t; } p[b] = a; sz[a] += sz[b]; return true; } } List<List<String>> accountsMerge(List<List<String>> accounts) { DSU d = new DSU(accounts.size()); Map<String, Integer> owner = new HashMap<>(); for (int i = 0; i < accounts.size(); i++) for (String e : accounts.get(i).subList(1, accounts.get(i).size())) { if (owner.containsKey(e)) d.union(owner.get(e), i); else owner.put(e, i); } Map<Integer, TreeSet<String>> groups = new HashMap<>(); for (var en : owner.entrySet()) groups.computeIfAbsent(d.find(en.getValue()), k -> new TreeSet<>()).add(en.getKey()); List<List<String>> res = new ArrayList<>(); for (var en : groups.entrySet()) { List<String> row = new ArrayList<>(); row.add(accounts.get(en.getKey()).get(0)); row.addAll(en.getValue()); res.add(row); } return res; }10 Number of islands II: count islands as land is added online
hardPositions arrive one at a time. Keep a DSU over the grid cells and a count. When a new land cell appears, count it as a new island, then union it with each land neighbour, decrementing the count for every union that merges two sets. Ignore a position that is already land. DFS would redo work per query; DSU makes each update near constant. Time O(k * alpha(m * n)), space O(m * n). Edge cases: duplicate positions (skip them), a cell joining up to four separate islands at once (count falls by 3), a single query.
pythonclass DSU: def __init__(self, n): self.p = list(range(n)) self.sz = [1] * n def find(self, x): while self.p[x] != x: self.p[x] = self.p[self.p[x]] x = self.p[x] return x def union(self, a, b): a, b = self.find(a), self.find(b) if a == b: return False if self.sz[a] < self.sz[b]: a, b = b, a self.p[b] = a self.sz[a] += self.sz[b] return True def num_islands2(m, n, positions): d = DSU(m * n) land, count, res = set(), 0, [] for r, c in positions: if (r, c) not in land: land.add((r, c)) count += 1 for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): nr, nc = r + dr, c + dc if (nr, nc) in land and d.union(r * n + c, nr * n + nc): count -= 1 res.append(count) return resjavaclass DSU { int[] p, sz; DSU(int n) { p = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) { int t = a; a = b; b = t; } p[b] = a; sz[a] += sz[b]; return true; } } List<Integer> numIslands2(int m, int n, int[][] positions) { DSU d = new DSU(m * n); boolean[] land = new boolean[m * n]; int count = 0; List<Integer> res = new ArrayList<>(); int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}}; for (int[] p : positions) { int id = p[0] * n + p[1]; if (!land[id]) { land[id] = true; count++; for (int[] dd : dirs) { int nr = p[0] + dd[0], nc = p[1] + dd[1]; if (nr >= 0 && nc >= 0 && nr < m && nc < n && land[nr * n + nc] && d.union(id, nr * n + nc)) count--; } } res.add(count); } return res; }
Frequently asked questions
What is the time complexity of union-find?
With path compression and union by rank or size each operation is O(alpha(n)) amortised, where alpha is the inverse Ackermann function and is at most 4 for any realistic n.
When should I use DSU instead of DFS?
Use DSU when edges are added over time and you need connectivity after each addition, or when you only need component counts. DFS is fine for a single static graph.
Can union-find detect cycles?
Yes in undirected graphs: an edge whose two endpoints already share a root creates a cycle. It does not detect cycles in directed graphs.
Is union-find asked in coding rounds?
It appears in graph rounds at product companies, often as redundant connection or accounts merge. The technical interview guide covers how such rounds are run.
Related guides
More in DSA Interview Questions
- Array interview questions with worked solutions
- Backtracking interview questions with worked solutions
- BFS (Breadth-First Search) Interview Questions
- Binary search interview questions with worked solutions
- Binary Search Tree Interview Questions and Answers
- Binary Tree Interview Questions and Answers
- Bit manipulation interview questions with worked solutions
- Bitmask DP Interview Questions
- Cyclic sort pattern interview questions with worked solutions
- DFS (Depth-First Search) Interview Questions
- Dijkstra and Shortest Path Interview Questions
- Divide and Conquer Interview Questions