Accounts Merge

MediumUnion-Find · Graph Components🧩 Union-Find LeetCode #721 ↗Updated Oct 30, 2026

Problem

Each entry of accounts is a list whose first element is a person's name and whose remaining elements are email addresses. Two accounts belong to the same person if they share at least one email (possibly through a chain of accounts); equal names alone prove nothing. Merge them and return each person as [name, emails sorted lexicographically, no duplicates], in any order.

Input[["Ann","a1@x.com","a2@x.com"],["Ann","a3@x.com","a1@x.com"],["Bob","b@x.com"],["Ann","a9@x.com"]]Output[["Ann","a1@x.com","a2@x.com","a3@x.com"],["Bob","b@x.com"],["Ann","a9@x.com"]]

Input[["Cy","c1@y","c2@y"],["Cy","c3@y"],["Cy","c2@y","c3@y"]]Output[["Cy","c1@y","c2@y","c3@y"]] (merged through a chain)

1 ≤ accounts.length ≤ 1000 · 2 ≤ accounts[i].length ≤ 10 · emails sharing an owner always have the same name

Try it yourself

Java

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

“Shares an email, directly or through a chain” is just connectivity. Union every account with the first account that owned each of its emails; each resulting set is one person, whose emails are then sorted.

PatternUnion-Find

Instinct Items get grouped by "connected", "same as" or "shares a" links and you keep asking which group something is in: merge sets with Union-Find.

Memory hack Find your boss, merge the bosses; squash the chain (path compression) and hang the short tree under the tall one (rank).

Open the Union-Find guide →

Approaches

Brute ForcePairwise Account Comparison + DFS

Time O(n²·k + N log N)Space O(n² + N)

Turn each account into a set of emails and compare every pair of accounts (O(k) per pair with hash sets); overlapping pairs become edges between accounts. Each connected component of accounts is one person. Here n = accounts, k = emails per account, N = total emails.

Java

public List<List<String>> accountsMerge(List<List<String>> accounts) {
    int n = accounts.size();
    List<Set<String>> sets = new ArrayList<>();
    for (List<String> acc : accounts) sets.add(new HashSet<>(acc.subList(1, acc.size())));
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (!Collections.disjoint(sets.get(i), sets.get(j))) {
                adj.get(i).add(j);
                adj.get(j).add(i);
            }
        }
    }
    boolean[] seen = new boolean[n];
    List<List<String>> result = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (seen[i]) continue;
        TreeSet<String> emails = new TreeSet<>();
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(i);
        seen[i] = true;
        while (!stack.isEmpty()) {
            int u = stack.pop();
            emails.addAll(sets.get(u));
            for (int v : adj.get(u)) {
                if (!seen[v]) {
                    seen[v] = true;
                    stack.push(v);
                }
            }
        }
        List<String> merged = new ArrayList<>();
        merged.add(accounts.get(i).get(0));
        merged.addAll(emails);
        result.add(merged);
    }
    return result;
}

Simple, but the n² pair checks dominate for many accounts.

BetterEmail Graph + DFS

Time O(N log N)Space O(N)

Make emails the nodes: link the first email of each account to every other email in it (a star per account). Two emails are the same person iff they are connected, so a DFS from each unvisited email collects one person, then sort.

Java

public List<List<String>> accountsMerge(List<List<String>> accounts) {
    Map<String, List<String>> graph = new HashMap<>();
    Map<String, String> owner = new HashMap<>();
    for (List<String> acc : accounts) {
        String first = acc.get(1);
        for (int i = 1; i < acc.size(); i++) {
            String email = acc.get(i);
            owner.put(email, acc.get(0));
            graph.computeIfAbsent(email, x -> new ArrayList<>());
            if (i > 1) { // star edges: first <-> email
                graph.get(first).add(email);
                graph.get(email).add(first);
            }
        }
    }
    Set<String> seen = new HashSet<>();
    List<List<String>> result = new ArrayList<>();
    for (String start : graph.keySet()) {
        if (!seen.add(start)) continue;
        List<String> component = new ArrayList<>();
        Deque<String> stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            String email = stack.pop();
            component.add(email);
            for (String next : graph.get(email)) {
                if (seen.add(next)) stack.push(next);
            }
        }
        Collections.sort(component);
        component.add(0, owner.get(start));
        result.add(component);
    }
    return result;
}

Near-linear; needs adjacency lists keyed by strings and an explicit traversal.

OptimalUnion-Find over Accounts

Time O(N·α(n) + N log N)Space O(N)

Keep a map email → first account that had it. When an email is seen again, union the current account with that owner. Afterwards group every email under the root account of its owner, sort each group and prepend the root account's name.

Java

public List<List<String>> accountsMerge(List<List<String>> accounts) {
    int n = accounts.size();
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    Map<String, Integer> firstOwner = new HashMap<>();
    for (int i = 0; i < n; i++) {
        List<String> acc = accounts.get(i);
        for (int j = 1; j < acc.size(); j++) {
            Integer prev = firstOwner.putIfAbsent(acc.get(j), i);
            if (prev != null) parent[find(parent, prev)] = find(parent, i);
        }
    }
    Map<Integer, List<String>> byRoot = new HashMap<>();
    for (Map.Entry<String, Integer> e : firstOwner.entrySet()) {
        int root = find(parent, e.getValue());
        byRoot.computeIfAbsent(root, r -> new ArrayList<>()).add(e.getKey());
    }
    List<List<String>> result = new ArrayList<>();
    for (Map.Entry<Integer, List<String>> e : byRoot.entrySet()) {
        List<String> emails = e.getValue();
        Collections.sort(emails);
        emails.add(0, accounts.get(e.getKey()).get(0));
        result.add(emails);
    }
    return result;
}

private int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]]; // path halving
        x = parent[x];
    }
    return x;
}

Same big-O as DFS (sorting dominates) but leaner: no graph, only an int array.

Pro tip

Union account indices, not email strings — the DSU stays a plain int[] and the name is just accounts.get(root).get(0).

At a glance

Level	Approach	Time	Space
Brute Force	Pairwise Account Comparison + DFS	`O(n²·k + N log N)`	`O(n² + N)`
Better	Email Graph + DFS	`O(N log N)`	`O(N)`
Optimal	Union-Find over Accounts	`O(N·α(n) + N log N)`	`O(N)`

Common pitfalls

Merging accounts just because the names match — two different people can share a name.
Only merging direct overlaps — chains (A~B, B~C) must collapse into one person.
Leaving duplicate emails or forgetting to sort them before prepending the name.

Interview tips

Reframe as “connected components where shared emails are edges”.
Mention the star trick: n-1 edges per account, not a full clique.
Note that sorting dominates, so DFS and union-find are equally fast asymptotically.

Pattern

Union-Find / connected components → group records that are linked transitively by any shared key.

My notes saved in this browser