Meta — Accounts Merge (Union-Find on Emails)

Problem Statement#

Given a list of accounts where each account is a list of strings [name, email1, email2, ...], merge accounts that share at least one email address. Return the merged accounts with sorted emails.

Constraints:

• 1 <= accounts.length <= 1000
• 2 <= accounts[i].length <= 10
• 1 <= accounts[i][j].length <= 30
• accounts[i][0] is a name string; remaining elements are emails

Input:  [["John","a@j.com","b@j.com"],["John","c@j.com"],["Mary","d@m.com"],["John","b@j.com","c@j.com"]]
Output: [["John","a@j.com","b@j.com","c@j.com"],["Mary","d@m.com"]]

Why This Problem Matters#

Accounts Merge (LeetCode 721) is a Meta signature problem that directly models their identity resolution system — one of the most critical backend services at Facebook. When two Facebook profiles share an email, they may represent the same real person. Merging these accounts efficiently and correctly is what this problem is about.

The problem maps directly to a graph connectivity problem: emails are nodes, and two emails sharing an account are connected by an edge. Connected components in this graph represent merged accounts. This can be solved with Union-Find or DFS/BFS.

Meta uses this problem to test whether candidates can model real-world scenarios as graphs and apply the right connectivity algorithm. Amazon and Google ask variants: "merge user records sharing a phone number" or "group items sharing a property." The Union-Find approach is the expected answer for the merge pattern.

The Core Insight#

Union-Find approach:

1. Map each email to its account's owner name
2. For each account, union all emails in that account together (they must be in the same component)
3. Group emails by their root representative (find operation)
4. For each group, sort the emails and prepend the owner name

DFS/BFS approach: Build an adjacency list where emails in the same account are connected. Run DFS/BFS to find all connected components.

Union-Find is more elegant and scales to streaming data. DFS is simpler to implement correctly.

Visual Dry Run#

accounts: [["John","a","b"],["John","c"],["John","b","c"]]

Solution (Optimal)#

from collections import defaultdict
 
class Solution:
    def accountsMerge(self, accounts: list) -> list:
        parent = {}
        email_to_name = {}
 
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
 
        def union(x, y):
            parent[find(x)] = find(y)
 
        for account in accounts:
            name = account[0]
            for email in account[1:]:
                if email not in parent:
                    parent[email] = email
                email_to_name[email] = name
                union(account[1], email)  # union all emails with the first one
 
        groups = defaultdict(list)
        for email in parent:
            groups[find(email)].append(email)
 
        result = []
        for root, emails in groups.items():
            result.append([email_to_name[root]] + sorted(emails))
 
        return result

var accountsMerge = function(accounts) {
    const parent = {};
    const emailToName = {};
 
    const find = (x) => {
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    };
 
    const union = (x, y) => {
        parent[find(x)] = find(y);
    };
 
    for (const account of accounts) {
        const name = account[0];
        for (let i = 1; i < account.length; i++) {
            const email = account[i];
            if (!(email in parent)) parent[email] = email;
            emailToName[email] = name;
            union(account[1], email);
        }
    }
 
    const groups = {};
    for (const email of Object.keys(parent)) {
        const root = find(email);
        if (!groups[root]) groups[root] = [];
        groups[root].push(email);
    }
 
    return Object.entries(groups).map(([root, emails]) =>
        [emailToName[root], ...emails.sort()]
    );
};

Time: O(N * K * alpha(NK)) where N is accounts, K is max emails per account; sorting adds O(NK*log(NK)) Space: O(N * K) — storing all emails in Union-Find

Common Mistakes#

• Not initializing each email's parent before calling union — causes KeyError
• Grouping by email instead of by root — multiple emails in same component have different "roots" before path compression
• Forgetting to sort emails in the output — problem requires sorted order
• Using account name as the union key instead of email — wrong entity
• Not applying path compression in find — causes O(N) per find instead of O(alpha(N))

Interview Tips#

• Explain the graph framing first: "Emails in the same account form a clique; find connected components"
• Union all emails in an account to the first email — this establishes the component representative
• The email_to_name map stores which person owns each email — needed to recover the name at the end
• DFS/BFS approach is simpler to code without Union-Find knowledge — offer as alternative
• Meta asks this to test identity resolution — mention the real-world connection explicitly

Follow-up Questions#

• How would you merge accounts that share a phone number instead of email? — Same algorithm, different key type
• What if the name associated with a merged email differs? — Use the first name seen or flag as conflict
• How do you handle streaming account additions? — Union-Find handles incremental adds naturally
• What if you need to detect potential fraud (too many email merges)? — Track component size; flag large components
• Can you solve this with DFS instead? — Build email adjacency graph, DFS to find connected components

Key Takeaways#

• Each email is a Union-Find node; emails in the same account are unioned together
• After all unions, group emails by their find() representative to get connected components
• Sort emails within each group — the problem requires sorted output per merged account
• The email_to_name map is needed to recover the account owner's name for the final result
• Meta tests this to verify graph connectivity thinking applied to identity deduplication systems
• Path compression in find() is essential for efficiency — naive find is O(N) per call
• DFS on an email adjacency graph is an equivalent O(N*K) approach that may be easier to code without Union-Find knowledge