Autocoder

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 / unionO(alpha(n)) amortised
OptimisationsPath compression, union by size or rank
Best forDynamic connectivity, cycle detection in undirected graphs
Not forDirected 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

Union-Find (Disjoint Set Union) Interview Questions: questions with worked answers

  1. 1

    Implement union-find with path compression and union by size

    easy

    Keep 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.

    python
    class 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
    java
    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;
        }
    }
  2. 2

    Number of provinces (connected components)

    easy

    Start 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.

    python
    class 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 count
    java
    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;
        }
    }
    
    
    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. 3

    Redundant connection: the edge that closes a cycle

    medium

    Add 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.

    python
    class 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 ans
    java
    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;
        }
    }
    
    
    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. 4

    Is the graph a valid tree?

    medium

    A 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.

    python
    class 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)
    java
    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;
        }
    }
    
    
    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. 5

    Satisfiability of equality equations

    medium

    Process 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.

    python
    def 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 True
    java
    boolean 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. 6

    Most stones removed in a grid

    medium

    A 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.

    python
    def 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)})
    java
    int 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. 7

    Longest consecutive sequence using union-find

    medium

    For 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.

    python
    class 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)
    java
    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;
        }
    }
    
    
    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. 8

    Smallest string after swaps at allowed index pairs

    medium

    Indices 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.

    python
    class 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)
    java
    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;
        }
    }
    
    
    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. 9

    Accounts merge: group emails belonging to the same person

    hard

    Two 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.

    python
    class 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()]
    java
    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;
        }
    }
    
    
    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. 10

    Number of islands II: count islands as land is added online

    hard

    Positions 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.

    python
    class 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 res
    java
    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;
        }
    }
    
    
    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

See all in this section