28 · Union-Find & Minimum Spanning Trees

#721 Accounts Merge

frequently reported atMeta Amazon Microsoft Google

the problem

In plain words

Each account is [name, email1, email2, …]. Two accounts belong to the same person if they share any email (names alone prove nothing). Merge them and return each person as [name, sorted emails…], in any order.

in [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

out [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

The first two Johns share johnsmith@mail.com; the third John shares nothing.

in [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]]

out [["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]

Nobody shares an email, so nothing merges — each account just gets its emails sorted.

1 ≤ accounts.length ≤ 1000
2 ≤ accounts[i].length ≤ 10
1 ≤ accounts[i][j].length ≤ 30
Names are English letters; emails are valid

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternUnion-Find (DSU)Graph DFS / BFS traversal

where this runsIdentity resolution — deciding that two sign-ups with a shared phone number or email are one customer — is this exact merge, run over far more records.

Emails are the nodes. Every account says "all these emails belong together" — union them with the account's first email. Each final set is one person.

solutions

From brute force to optimal

Connect each email to the first email of its account (a star), then each DFS component is one person.

Build email → neighbours and email → name maps.
DFS (iterative, with ArrayDeque) from each unseen email to collect its component.
Sort the component and prepend the name.

timeO(N log N)

N = total emails. Building and traversing is O(N); sorting the groups dominates.

spaceO(N)

Graph, maps and visited set.

javajava.util.*

1class Solution {2    public List<List<String>> accountsMerge(List<List<String>> accounts) {3        Map<String, List<String>> graph = new HashMap<>(); // email → neighbouring emails4        Map<String, String> owner = new HashMap<>();       // email → name5        for (List<String> acc : accounts) {6            String first = acc.get(1);7            for (int i = 1; i < acc.size(); i++) {8                String email = acc.get(i);9                owner.put(email, acc.get(0));10                graph.computeIfAbsent(email, k -> new ArrayList<>());11                if (i > 1) { // star: link every email to the first one of its account12                    graph.get(first).add(email);13                    graph.get(email).add(first);14                }15            }16        }17        Set<String> seen = new HashSet<>();18        List<List<String>> result = new ArrayList<>();19        for (String start : graph.keySet()) {20            if (!seen.add(start)) continue;21            List<String> emails = new ArrayList<>();22            ArrayDeque<String> stack = new ArrayDeque<>();23            stack.push(start);24            while (!stack.isEmpty()) {            // iterative DFS: one component = one person25                String e = stack.pop();26                emails.add(e);27                for (String nb : graph.get(e)) if (seen.add(nb)) stack.push(nb);28            }29            Collections.sort(emails);30            emails.add(0, owner.get(start));31            result.add(emails);32        }33        return result;34    }35}

Map-based DSU: union every email with its account's first email, then group by root.

parent.putIfAbsent(email, email) and remember email → name.
For each account, union all its emails with the first one.
Group emails by find(email) into TreeSets (sorted), then build the output rows.

timeO(N log N)

This map DSU uses path compression only, so finds are O(log N) amortized; sorting each group (TreeSet inserts) also costs a log. Add union by size and the DSU part drops to O(N·α(N)) — the sort still dominates.

spaceO(N)

parent map, owner map and the groups.

javajava.util.*

1class Solution {2    private final Map<String, String> parent = new HashMap<>();3 4    private String find(String x) {5        String p = parent.get(x);6        if (!p.equals(x)) {7            p = find(p);8            parent.put(x, p); // path compression9        }10        return p;11    }12 13    public List<List<String>> accountsMerge(List<List<String>> accounts) {14        Map<String, String> owner = new HashMap<>();15        for (List<String> acc : accounts) {16            for (int i = 1; i < acc.size(); i++) {17                parent.putIfAbsent(acc.get(i), acc.get(i)); // every email starts as its own set18                owner.put(acc.get(i), acc.get(0));19            }20        }21        for (List<String> acc : accounts) {22            String root = find(acc.get(1));23            for (int i = 2; i < acc.size(); i++) {24                String other = find(acc.get(i));25                if (!other.equals(root)) parent.put(other, root); // union with the first email26            }27        }28        Map<String, TreeSet<String>> groups = new HashMap<>(); // root → sorted emails29        for (String email : parent.keySet()) {30            groups.computeIfAbsent(find(email), k -> new TreeSet<>()).add(email);31        }32        List<List<String>> result = new ArrayList<>();33        for (Map.Entry<String, TreeSet<String>> g : groups.entrySet()) {34            List<String> row = new ArrayList<>();35            row.add(owner.get(g.getKey()));36            row.addAll(g.getValue());37            result.add(row);38        }39        return result;40    }41}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    private final Map<String, String> parent = new HashMap<>();3 4    private String find(String x) {5        String p = parent.get(x);6        if (!p.equals(x)) {7            p = find(p);8            parent.put(x, p); // path compression9        }10        return p;11    }12 13    public List<List<String>> accountsMerge(List<List<String>> accounts) {14        Map<String, String> owner = new HashMap<>();15        for (List<String> acc : accounts) {16            for (int i = 1; i < acc.size(); i++) {17                parent.putIfAbsent(acc.get(i), acc.get(i)); // every email starts as its own set18                owner.put(acc.get(i), acc.get(0));19            }20        }21        for (List<String> acc : accounts) {22            String root = find(acc.get(1));23            for (int i = 2; i < acc.size(); i++) {24                String other = find(acc.get(i));25                if (!other.equals(root)) parent.put(other, root); // union with the first email26            }27        }28        Map<String, TreeSet<String>> groups = new HashMap<>(); // root → sorted emails29        for (String email : parent.keySet()) {30            groups.computeIfAbsent(find(email), k -> new TreeSet<>()).add(email);31        }32        List<List<String>> result = new ArrayList<>();33        for (Map.Entry<String, TreeSet<String>> g : groups.entrySet()) {34            List<String> row = new ArrayList<>();35            row.add(owner.get(g.getKey()));36            row.addAll(g.getValue());37            result.add(row);38        }39        return result;40    }41}

in the room

How to say it in the interview

talk track

Clarify: same name does not mean same person; only shared emails do.
Say why you union with the first email: it makes each account one connected star without adding k² edges.
Both DFS and DSU are O(N log N) because of the final sort — pick the one you can write cleanly.

traps

Merging by name.
Forgetting to sort the emails in each output row.
Duplicate emails inside one account — sets handle them; lists would repeat them.

what they ask next

Follow-ups

Accounts keep arriving one at a time?

Union-find is built for this: each new account is a few unions, near O(1) each. Build the sorted groups only when someone asks for them.

People can also be linked by a shared phone number?

Make phones nodes too, in the same DSU. Prefix the keys ("e:" for email, "p:" for phone) so the two kinds never clash.

before you submit

Edge cases to test

Same name, no shared email → different people, separate rows.
Two accounts linked only through a third account must still merge.
The same email listed twice inside one account must appear once.
A single account with a single email → one row.

practise next