Accounts Merge

NeetCode: Accounts Merge · LeetCode: 721. Accounts Merge · Difficulty: Medium

Each account is a list whose first element is a name and whose remaining elements are emails. Two accounts belong to the same person if they share at least one email. Merge such accounts: the result for each person is the name followed by their distinct emails in sorted order. Different people may have the same name. Return the merged accounts in any order; the examples below sort them so the output is deterministic (the optimal solution builds its result from a HashMap, whose iteration order is unspecified).

Example

Text

Input:
  [John, johnsmith@mail.com, john_newyork@mail.com]
  [John, johnsmith@mail.com, john00@mail.com]
  [Mary, mary@mail.com]
  [John, johnnybravo@mail.com]

Output:
  [John, john00@mail.com, john_newyork@mail.com, johnsmith@mail.com]
  [John, johnnybravo@mail.com]
  [Mary, mary@mail.com]

Brute force: keep merging sets until nothing changes

Turn each account into a TreeSet of emails (a sorted set without duplicates). Repeat: look for any two sets that intersect and merge them into one; stop when a full pass finds no intersecting pair. Collections.disjoint tests whether two sets share no element. It is simple, but every merge can create new overlaps, so you rescan pairs many times.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.TreeSet;

public class Main {
    static class Solution {
        public List<List<String>> accountsMerge(List<List<String>> accounts) {
            List<String> names = new ArrayList<>();
            List<TreeSet<String>> groups = new ArrayList<>();
            for (List<String> a : accounts) {
                names.add(a.get(0));
                groups.add(new TreeSet<>(a.subList(1, a.size())));
            }
            boolean merged = true;
            while (merged) {
                merged = false;
                search:
                for (int i = 0; i < groups.size(); i++) {
                    for (int j = i + 1; j < groups.size(); j++) {
                        if (!Collections.disjoint(groups.get(i), groups.get(j))) {
                            groups.get(i).addAll(groups.remove(j));
                            names.remove(j);
                            merged = true;
                            break search;
                        }
                    }
                }
            }
            List<List<String>> out = new ArrayList<>();
            for (int i = 0; i < groups.size(); i++) {
                List<String> row = new ArrayList<>();
                row.add(names.get(i));
                row.addAll(groups.get(i));
                out.add(row);
            }
            return out;
        }
    }

    static int compareRows(List<String> a, List<String> b) {
        for (int i = 0; i < Math.min(a.size(), b.size()); i++) {
            int c = a.get(i).compareTo(b.get(i));
            if (c != 0) {
                return c;
            }
        }
        return Integer.compare(a.size(), b.size());
    }

    public static void main(String[] args) {
        List<List<String>> accounts = List.of(
            List.of("John", "johnsmith@mail.com", "john_newyork@mail.com"),
            List.of("John", "johnsmith@mail.com", "john00@mail.com"),
            List.of("Mary", "mary@mail.com"),
            List.of("John", "johnnybravo@mail.com"));
        Solution s = new Solution();
        List<List<String>> merged = s.accountsMerge(accounts);
        merged.sort(Main::compareRows);
        for (List<String> row : merged) {
            System.out.println(row);
        }
        System.out.println(s.accountsMerge(new ArrayList<>()));
    }
}

Output

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

Each merge removes one group, so there are at most A - 1 merges. After each merge the scan restarts and examines up to A^2 pairs, each intersection test costing up to the size of a set. With A accounts and L the largest set size, that is roughly cubic in A. Time: O(A^3 * L). Space: O(E) for E total emails.

Optimal: union-find over account indices

Treat each account as a node. Walk the accounts and keep a map from email to the first account index that owned it. When an email is seen again, union the current account with that owner. Afterwards, group every account's emails by its root, sort each group and prepend the name. find uses path halving, a form of path compression in which each visited node is pointed at its grandparent.

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeSet;

public class Main {
    static class Solution {
        private int[] parent;

        private int find(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]]; // path halving: point to the grandparent
                x = parent[x];
            }
            return x;
        }

        public List<List<String>> accountsMerge(List<List<String>> accounts) {
            parent = new int[accounts.size()];
            for (int i = 0; i < parent.length; i++) {
                parent[i] = i;
            }
            Map<String, Integer> owner = new HashMap<>(); // email -> first account
            for (int i = 0; i < accounts.size(); i++) {
                List<String> account = accounts.get(i);
                for (String email : account.subList(1, account.size())) {
                    Integer j = owner.get(email);
                    if (j != null) {
                        parent[find(i)] = find(j);
                    } else {
                        owner.put(email, i);
                    }
                }
            }
            // Group emails by root account; TreeSet removes duplicates and sorts.
            Map<Integer, TreeSet<String>> groups = new HashMap<>();
            for (int i = 0; i < accounts.size(); i++) {
                List<String> account = accounts.get(i);
                groups.computeIfAbsent(find(i), k -> new TreeSet<>())
                      .addAll(account.subList(1, account.size()));
            }
            List<List<String>> out = new ArrayList<>();
            for (Map.Entry<Integer, TreeSet<String>> e : groups.entrySet()) {
                List<String> row = new ArrayList<>();
                row.add(accounts.get(e.getKey()).get(0));
                row.addAll(e.getValue());
                out.add(row);
            }
            return out;
        }
    }

    static int compareRows(List<String> a, List<String> b) {
        for (int i = 0; i < Math.min(a.size(), b.size()); i++) {
            int c = a.get(i).compareTo(b.get(i));
            if (c != 0) {
                return c;
            }
        }
        return Integer.compare(a.size(), b.size());
    }

    public static void main(String[] args) {
        List<List<String>> accounts = List.of(
            List.of("John", "johnsmith@mail.com", "john_newyork@mail.com"),
            List.of("John", "johnsmith@mail.com", "john00@mail.com"),
            List.of("Mary", "mary@mail.com"),
            List.of("John", "johnnybravo@mail.com"));
        Solution s = new Solution();
        List<List<String>> merged = s.accountsMerge(accounts);
        merged.sort(Main::compareRows);
        for (List<String> row : merged) {
            System.out.println(row);
        }
        System.out.println(s.accountsMerge(new ArrayList<>()));
    }
}

Output

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

Walk-through: johnsmith@mail.com is first owned by account 0; account 1 sees it again, so 1 is unioned with 0. Accounts 2 and 3 share nothing, so they stay alone. Grouping gives {0, 1} merged (3 sorted emails), plus Mary and the other John.

Accounts in one group always share a name, so the root account supplies it. With E total emails of length up to L: Time: O(E * L * log E), dominated by sorting (the union-find part is near-linear). Space: O(E * L).

How to explain it in an interview

Brute force: repeatedly merge any two email sets that intersect until none do; roughly cubic in the number of accounts.
Key idea: "shares an email" is a connectivity relation, so union-find on account indices groups accounts in near-linear time.
Steps: (1) parent array plus find with path compression (here, path halving); (2) map each email to the first account that has it, and union on a repeat; (3) group emails by root in a TreeSet (dedup plus sort); (4) output name (from the root account) followed by the sorted emails.
Complexity: O(E log E) comparisons for sorting (times string length), O(E) space.
Pitfalls: the same name does not mean the same person, so merge by email only. A DFS over an email graph is an equivalent alternative.