Accounts Merge

Medium Graphs Connected Components Original on LeetCode

Accounts Merge is a medium graphs problem solved with the connected components pattern. The best approach, optimal (union-find over accounts), runs in O(N log N) time and O(N) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (merge pairs until nothing changes) up.

Problem

You are given a list accounts. Each entry is a list of strings: the first string is the owner’s name, and the rest are email addresses belonging to that account.

Two accounts belong to the same person if they have at least one email in common (directly, or through a chain of other accounts). Different people can have the same name, and one person may have many accounts, all under the same name.

Merge the accounts and return one entry per person: the name first, followed by all of that person’s distinct emails in sorted order. The entries themselves may be returned in any order.

Examples

Example 1

Input
accounts = [["Kite", "kite@a.com", "k.t@b.com"], ["Moss", "moss@c.com"], ["Kite", "k.t@b.com", "kite99@d.com"]]
Output
[["Kite", "k.t@b.com", "kite99@d.com", "kite@a.com"], ["Moss", "moss@c.com"]]
Why
The two Kite accounts share k.t@b.com, so they belong to one person and are merged; their emails are listed in sorted order.

Example 2

Input
accounts = [["Lark", "lark@x.io"], ["Lark", "lark2@y.io"]]
Output
[["Lark", "lark@x.io"], ["Lark", "lark2@y.io"]]
Why
Same name but no shared email, so these are two different people and stay separate.

Example 3

Input
accounts = [["Fern", "a@f.io", "b@f.io"], ["Fern", "c@f.io"], ["Fern", "b@f.io", "c@f.io"]]
Output
[["Fern", "a@f.io", "b@f.io", "c@f.io"]]
Why
The first and second accounts share nothing directly, but the third one links them, so all three merge.

Constraints

  • 1 <= accounts.length <= 1000
  • 2 <= accounts[i].length <= 10
  • 1 <= accounts[i][j].length <= 30
  • accounts[i][0] is made of English letters; every email is lowercase letters, digits, . and @.
  • Accounts that share an email always have the same name.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (merge pairs until nothing changes)O(n³ · k)O(n · k)
Optimal (Union-Find over accounts)O(N log N)O(N)

1Brute force (merge pairs until nothing changes)

TimeO(n³ · k)Up to n merges, each preceded by a scan over O(n²) pairs, and each intersection test costs O(k) for k emails per group (sets can grow, so k is the group size).
SpaceO(n · k)The groups together hold every email once.

Keep a list of groups, each with a name and a set of emails. Repeatedly look for two groups whose email sets overlap and merge them. When no pair overlaps any more, every group is one person.

  1. Create one group per account: its name and a set of its emails.
  2. Search all pairs (i, j). If the sets intersect, add group j's emails into group i, remove group j and start the search again.
  3. When a full search finds no overlap, output each group as [name, sorted emails...].
class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        List<String> names = new ArrayList<>();
        List<Set<String>> sets = new ArrayList<>();
        for (List<String> acc : accounts) {
            names.add(acc.get(0));
            sets.add(new HashSet<>(acc.subList(1, acc.size())));
        }
        boolean changed = true;
        while (changed) {
            changed = false;
            search:
            for (int i = 0; i < sets.size(); i++) {
                for (int j = i + 1; j < sets.size(); j++) {
                    if (!Collections.disjoint(sets.get(i), sets.get(j))) {
                        sets.get(i).addAll(sets.get(j));
                        sets.remove(j);
                        names.remove(j);
                        changed = true;
                        break search;
                    }
                }
            }
        }
        List<List<String>> result = new ArrayList<>();
        for (int i = 0; i < sets.size(); i++) {
            List<String> emails = new ArrayList<>(sets.get(i));
            Collections.sort(emails);
            emails.add(0, names.get(i));
            result.add(emails);
        }
        return result;
    }
}

2Optimal (Union-Find over accounts)

TimeO(N log N)N is the total number of emails. Union-Find with path compression is nearly O(1) per operation, so sorting the emails inside each group dominates.
SpaceO(N)The owner map and the buckets each hold every distinct email once.

Give every account an index in a disjoint-set structure. Walk the emails with a map from email to the first account that owned it; when an email shows up again, union the current account with that owner. Afterwards, every email belongs to the root of its first owner, so grouping emails by root gives one list per person.

  1. parent[i] = i for every account.
  2. For each account i and each email e: if e is in owner, union(i, owner[e]); else owner[e] = i.
  3. For each (email, account) in owner, append the email to the bucket of find(account).
  4. For each bucket, sort the emails and prepend the name of the root account.
class Solution {
    private int[] parent;

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        int n = accounts.size();
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        Map<String, Integer> owner = new HashMap<>();
        for (int i = 0; i < n; i++) {
            List<String> acc = accounts.get(i);
            for (int j = 1; j < acc.size(); j++) {
                String email = acc.get(j);
                Integer o = owner.get(email);
                if (o == null) owner.put(email, i);
                else union(i, o);
            }
        }

        Map<Integer, List<String>> groups = new HashMap<>();
        for (Map.Entry<String, Integer> e : owner.entrySet()) {
            groups.computeIfAbsent(find(e.getValue()), k -> new ArrayList<>()).add(e.getKey());
        }

        List<List<String>> result = new ArrayList<>();
        for (Map.Entry<Integer, List<String>> g : groups.entrySet()) {
            List<String> emails = g.getValue();
            Collections.sort(emails);
            emails.add(0, accounts.get(g.getKey()).get(0));
            result.add(emails);
        }
        return result;
    }

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

    private void union(int a, int b) {
        parent[find(a)] = find(b);
    }
}

Edge cases to test

  • A single account
  • Two accounts with the same name and no common email (different people)
  • Accounts linked only through a chain of other accounts
  • The same email listed twice inside one account
  • Every account belonging to one person

Hints

Hint 1

Two accounts belong to the same person if they share an email, and this relation is transitive. What does that remind you of?

Hint 2

Think of accounts (or emails) as nodes and shared emails as edges. Each person is a connected component.

Hint 3

Union-Find: map each email to the first account that contained it and union every later account that contains the same email with that one.

FAQ

What is the best time complexity for Accounts Merge?

Optimal (Union-Find over accounts) runs in O(N log N) time and O(N) extra space. N is the total number of emails. Union-Find with path compression is nearly O(1) per operation, so sorting the emails inside each group dominates.

Which pattern does Accounts Merge use?

It is a graphs problem that uses the connected components pattern. Other problems with the same pattern: Number of Provinces, Number of Islands, Evaluate Division.

Is there a brute force solution for Accounts Merge?

Yes. Brute force (merge pairs until nothing changes) takes O(n³ · k) time and O(n · k) space. Keep a list of groups, each with a name and a set of emails.

Which edge cases should I test for Accounts Merge?

A single account; Two accounts with the same name and no common email (different people); Accounts linked only through a chain of other accounts; The same email listed twice inside one account; Every account belonging to one person.