☕ DSA Java Articles

Topics › Graphs › MinimumSpanningTree/Disjoint Set and Problems

Accounts merge

Hard TUF ID 511 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a list of accounts. Each account is a list of strings: the first is a name, the rest are emails belonging to that account. Two accounts belong to the same person if they share at least one email, and this is transitive: if A shares an email with B and B shares one with C, all three are the same person. Two accounts with the same name but no common email may belong to different people.

Merge the accounts and return them as lists of the form [name, emails...] with the emails in sorted (lexicographic) order and each email listed once. The accounts themselves may be returned in any order.

Constraints: 1 ≤ accounts.length ≤ 1000, 2 ≤ accounts[i].length ≤ 10, every email of a person has that person’s name.

Example 1

accounts = [["John","j1@com","j2@com","j3@com"], ["John","j4@com"], ["Raj","r1@com","r2@com"],
            ["John","j1@com","j5@com"], ["Raj","r2@com","r3@com"], ["Mary","m1@com"]]
answer   = [["John","j1@com","j2@com","j3@com","j5@com"], ["John","j4@com"],
            ["Raj","r1@com","r2@com","r3@com"], ["Mary","m1@com"]]
// accounts 0 and 3 share j1@com; 2 and 4 share r2@com; the second John is someone else

Example 2

accounts = [["A","a@x","b@x"], ["A","c@x","d@x"], ["A","b@x","c@x"]]
answer   = [["A","a@x","b@x","c@x","d@x"]]
// 0 and 1 share nothing, but account 2 bridges them, so all three merge

Example 2 is the case that breaks naive one-pass merging: when accounts 0 and 1 are compared, they look unrelated.

Approach 1: Brute force, merge until nothing changes

Intuition. Keep each account as a set of emails. Whenever two sets intersect they must be the same person, so merge them into one. A merge can create a new intersection with some third account (example 2), so repeat the whole scan until a full pass makes no merge. At that point no two remaining sets intersect, which is precisely the definition of the answer.

Algorithm.

  1. Turn each account into a name plus a HashSet of its emails.
  2. Scan all pairs (i, j). On the first intersecting pair, add set j into set i, delete account j, and restart the scan.
  3. When a scan finds no intersecting pair, sort each set and prepend its name.
static List<List<String>> bruteForce(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 merged = true;
    while (merged) {                                         // restart the scan after every merge
        merged = false;
        for (int i = 0; i < sets.size() && !merged; i++) {
            for (int j = i + 1; j < sets.size() && !merged; j++) {
                if (!Collections.disjoint(sets.get(i), sets.get(j))) {
                    sets.get(i).addAll(sets.remove(j));
                    names.remove(j);
                    merged = true;
                }
            }
        }
    }
    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;
}

Complexity. Time O(n^3 · k) in the worst case, with n accounts of up to k emails: there can be n - 1 merges, each preceded by a scan over O(n^2) pairs, and an intersection test costs O(k) set lookups. Space O(n · k) for the sets. Correct, but the repeated rescans waste almost all of the work.

Approach 2: Graph of emails plus DFS

Intuition. “Shares an email, transitively” is graph connectivity in disguise. Make every distinct email a vertex. Inside one account, all emails belong to the same person, so connect them. We do not need all pairs: linking every email of the account to the account’s first email (a star) already makes them connected, using k - 1 edges instead of k(k-1)/2. An email that appears in two accounts is a single vertex that sits in both stars, and that is what joins the accounts.

Each connected component of this graph is one person. A DFS from any unvisited email collects that person’s complete email list. A side map owner remembers the name for each email.

Algorithm.

  1. For every account, create a vertex per email, record owner[email] = name, and add an undirected edge between the account’s first email and each of its other emails.
  2. For every email not yet visited, run an iterative DFS and collect the component.
  3. Sort the component, prepend the owner’s name, and add it to the result.
static List<List<String>> dfsEmails(List<List<String>> accounts) {
    Map<String, List<String>> graph = new HashMap<>();
    Map<String, String> owner = new HashMap<>();
    for (List<String> acc : accounts) {
        for (int i = 1; i < acc.size(); i++) {
            String email = acc.get(i);
            graph.computeIfAbsent(email, k -> new ArrayList<>());
            owner.put(email, acc.get(0));
            if (i > 1) {                                     // link every email to the account's first email
                graph.get(acc.get(1)).add(email);
                graph.get(email).add(acc.get(1));
            }
        }
    }
    Set<String> visited = new HashSet<>();
    List<List<String>> result = new ArrayList<>();
    Deque<String> stack = new ArrayDeque<>();
    for (String start : graph.keySet()) {
        if (!visited.add(start)) continue;
        List<String> group = new ArrayList<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            String e = stack.pop();
            group.add(e);
            for (String next : graph.get(e)) {
                if (visited.add(next)) stack.push(next);
            }
        }
        Collections.sort(group);
        group.add(0, owner.get(start));
        result.add(group);
    }
    return result;
}

Complexity. Let N be the total number of emails across all accounts. Building the graph and the DFS are O(N) hash operations (each string hash is O(L) for email length L, treated as constant here). Sorting the groups costs O(N log N) in total. Space O(N) for the graph, the owner map and the visited set.

Approach 3: Disjoint Set over accounts

Intuition. Instead of making emails the vertices, make the accounts the vertices and let shared emails be the reason to union them. Walk through the emails while remembering, in a map, the first account where each email appeared. If an email shows up again in account i, its earlier owner and i are the same person: union(firstOwner, i). After the pass, every account’s root identifies its person. Finally group each email under the root of its first owner and output the groups.

This avoids building any graph. Each email is touched once to union and once to group.

static final class DisjointSet {
    final int[] parent, size;

    DisjointSet(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);   // path compression
        return parent[x];
    }

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;                         // already in the same set
        if (size[ra] < size[rb]) {
            int t = ra;
            ra = rb;
            rb = t;
        }
        parent[rb] = ra;                                    // hang the smaller tree under the larger
        size[ra] += size[rb];
        return true;
    }
}

Algorithm.

  1. Create a Disjoint Set over n account indices and an empty map firstOwner from email to account index.
  2. For every account i and every email e in it: if e is new, store firstOwner[e] = i; otherwise union(firstOwner[e], i).
  3. For every (email, owner) in the map, append the email to the list of find(owner).
  4. For each root, sort its emails and prepend accounts[root][0].
static List<List<String>> disjointSet(List<List<String>> accounts) {
    int n = accounts.size();
    DisjointSet ds = new DisjointSet(n);
    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) ds.union(prev, i);            // shared email: same person
        }
    }
    Map<Integer, List<String>> byRoot = new HashMap<>();
    for (Map.Entry<String, Integer> e : firstOwner.entrySet()) {
        byRoot.computeIfAbsent(ds.find(e.getValue()), k -> 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;
}

Dry run on example 1 (accounts numbered 0 to 5):

account emails new emails go to map repeated email union
0 John j1, j2, j3 j1→0, j2→0, j3→0    
1 John j4 j4→1    
2 Raj r1, r2 r1→2, r2→2    
3 John j1, j5 j5→3 j1 (owner 0) union(0, 3)
4 Raj r2, r3 r3→4 r2 (owner 2) union(2, 4)
5 Mary m1 m1→5    

Roots are 0 (j1, j2, j3, j5), 1 (j4), 2 (r1, r2, r3) and 5 (m1). Using accounts[root][0] for the name is safe because every account in a group has the same name.

Complexity. Time O(N · α(n) + N log N): one map operation and at most one union per email, plus sorting. Space O(N + n) for the map, the groups and the Disjoint Set arrays.

Approaches 2 and 3 have the same asymptotic cost. The Disjoint Set version tends to be the shorter one to write correctly in an interview, and it extends naturally if accounts keep arriving over time.

Edge cases and pitfalls