721. Accounts Merge (Medium)

Problem

You are given a list of accounts where each element is a list: [name, email1, email2, ...]. Two accounts belong to the same person if they share at least one email. Merge all accounts belonging to the same person. The output order of accounts and emails within accounts does not matter, but emails within an account must be sorted.

Example

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

Output (order may vary):

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

LeetCode 721 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach: Union-Find on emails

The core observation: two accounts are the same person iff they share at least one email. Treat emails as graph nodes; union every email in an account under that account’s first email. Then group all emails by their root, attach the name, and sort.

def accounts_merge(accounts):
    parent = {}                                             # L1: email -> parent email

    def find(x):                                           # L2: path-compressed find
        if parent[x] != x:
            parent[x] = find(parent[x])                   # L3: full path compression
        return parent[x]

    def union(a, b):
        parent[find(a)] = find(b)                         # L4: O(alpha) link roots

    email_to_name = {}                                     # L5: email -> account owner name

    for account in accounts:                               # L6: O(n) over all accounts
        name = account[0]
        for email in account[1:]:                          # L7: O(k) per account
            if email not in parent:
                parent[email] = email                      # L8: O(1) init new email
            email_to_name[email] = name                   # L9: O(1) record owner
            union(account[1], email)                       # L10: O(alpha) union under first email

    from collections import defaultdict
    groups = defaultdict(list)                             # L11: root -> list of emails
    for email in parent:                                   # L12: O(n*k) over all emails
        groups[find(email)].append(email)                  # L13: O(alpha) find + O(1) append

    result = []
    for root, emails in groups.items():                    # L14: O(n*k) iterate groups
        result.append([email_to_name[root]] + sorted(emails))  # L15: O(k log k) sort per group

    return result

function accountsMerge(accounts: string[][]): string[][] {
    const parent = new Map<string, string>();               // L1: email -> parent email
    const emailToName = new Map<string, string>();          // L5: email -> account owner name

    function find(x: string): string {                     // L2: path-compressed find
        if (parent.get(x) !== x) parent.set(x, find(parent.get(x)!));  // L3: compression
        return parent.get(x)!;
    }

    function union(a: string, b: string): void {
        parent.set(find(a), find(b));                      // L4: O(alpha) link roots
    }

    for (const account of accounts) {                      // L6: O(n) over all accounts
        const name = account[0];
        for (const email of account.slice(1)) {            // L7: O(k) per account
            if (!parent.has(email)) parent.set(email, email);  // L8: O(1) init new email
            emailToName.set(email, name);                  // L9: O(1) record owner
            union(account[1], email);                      // L10: O(alpha) union under first email
        }
    }

    const groups = new Map<string, string[]>();            // L11: root -> list of emails
    for (const email of parent.keys()) {                   // L12: over all emails
        const root = find(email);
        if (!groups.has(root)) groups.set(root, []);
        groups.get(root)!.push(email);                     // L13: O(alpha) find + append
    }

    const result: string[][] = [];
    for (const [root, emails] of groups) {                 // L14: iterate groups
        result.push([emailToName.get(root)!, ...emails.sort()]);  // L15: O(k log k) sort
    }
    return result;
}

struct UnionFind {
    var parent: [Int]
    var rank: [Int]
    init(_ count: Int) { parent = Array(0..<count); rank = Array(repeating: 0, count: count) }
    mutating func find(_ value: Int) -> Int {
        if parent[value] != value { parent[value] = find(parent[value]) }
        return parent[value]
    }
    mutating func union(_ left: Int, _ right: Int) -> Bool {
        var a = find(left), b = find(right)
        if a == b { return false }
        if rank[a] < rank[b] { swap(&a, &b) }
        parent[b] = a
        if rank[a] == rank[b] { rank[a] += 1 }
        return true
    }
}

final class Solution {
    func accountsMerge(_ accounts: [[String]]) -> [[String]] {
        var unionFind = UnionFind(accounts.count), owner: [String: Int] = [:]
        for index in accounts.indices {
            for email in accounts[index].dropFirst() {
                if let previous = owner[email] { _ = unionFind.union(index, previous) } else { owner[email] = index }
            }
        }
        var groups: [Int: [String]] = [:]
        for email in owner.keys.sorted() { groups[unionFind.find(owner[email]!), default: []].append(email) }
        return groups.map { root, emails in [accounts[root][0]] + emails }
            .sorted { $0.joined(separator: "\u{0}") < $1.joined(separator: "\u{0}") }
    }
}

Where the time goes, line by line

Variables: n = number of accounts, k = average emails per account.

Line	Per-call cost	Times executed	Contribution
L6 (account loop)	$O(1)$	n	$O(n)$
L7 (email loop)	$O(1)$	n * k total	$O(n * k)$
L8 (init parent)	$O(1)$	n * k	$O(n * k)$
L10 (union)	$O(alpha)$	*n k**	*$O(n k * alpha)$ ← dominates**
L12 (group pass)	$O(alpha)$ per find	n * k	$O(n * k * alpha)$
L15 (sort)	$O(k log k)$	n groups	*$O(n k * log k)$ ← dominates**

Complexity

Time: $O(n * k * log k)$ , driven by L15 (sorting emails within each merged group).
Space: $O(n * k)$ for the parent and email_to_name maps.

Why union under the first email?

Every email in an account must be reachable from every other email in that account (they all belong to the same person). Unioning each email with account[1] (the first email) creates a star topology centered on the first email. Path compression flattens this during subsequent finds, so the root correctly represents the merged group.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Step	Cost
Build Union-Find (all union calls)	$O(n * k * alpha)$
Group emails by root	$O(n * k * alpha)$
Sort each group	$O(n * k * log k)$
Total	*$O(n k * log k)$**

from collections import defaultdict

def accounts_merge(accounts):
    parent = {}

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(a, b):
        parent[find(a)] = find(b)

    email_to_name = {}

    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)

    groups = defaultdict(list)
    for email in parent:
        groups[find(email)].append(email)

    return [[email_to_name[root]] + sorted(emails) for root, emails in groups.items()]

def _run_tests():
    def normalize(result):
        return sorted([row[0:1] + sorted(row[1:]) for row in result])

    # Example from problem: two Johns merge, one John and Mary stay separate
    a1 = [
        ["John", "johnsmith@mail.com", "john_newyork@mail.com"],
        ["John", "johnsmith@mail.com", "john00@mail.com"],
        ["Mary", "mary@mail.com"],
        ["John", "johnnybravo@mail.com"],
    ]
    r1 = normalize(accounts_merge(a1))
    expected1 = normalize([
        ["John", "john00@mail.com", "john_newyork@mail.com", "johnsmith@mail.com"],
        ["Mary", "mary@mail.com"],
        ["John", "johnnybravo@mail.com"],
    ])
    assert r1 == expected1, f"Expected {expected1}, got {r1}"

    # Single account
    a2 = [["Alice", "a@x.com"]]
    assert normalize(accounts_merge(a2)) == [["Alice", "a@x.com"]]

    # All accounts share one email, all merge
    a3 = [["A", "x@y.com", "a@b.com"], ["A", "x@y.com", "c@d.com"]]
    r3 = normalize(accounts_merge(a3))
    assert r3 == [["A", "a@b.com", "c@d.com", "x@y.com"]]

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function accountsMerge(accounts: string[][]): string[][] {
    const parent = new Map<string, string>();
    const emailToName = new Map<string, string>();

    function find(x: string): string {
        if (parent.get(x) !== x) parent.set(x, find(parent.get(x)!));
        return parent.get(x)!;
    }

    for (const account of accounts) {
        const name = account[0];
        for (const email of account.slice(1)) {
            if (!parent.has(email)) parent.set(email, email);
            emailToName.set(email, name);
            parent.set(find(account[1]), find(email));
        }
    }

    const groups = new Map<string, string[]>();
    for (const email of parent.keys()) {
        const root = find(email);
        if (!groups.has(root)) groups.set(root, []);
        groups.get(root)!.push(email);
    }

    const result: string[][] = [];
    for (const [root, emails] of groups)
        result.push([emailToName.get(root)!, ...emails.sort()]);
    return result;
}

function normalize(result: string[][]): string {
    return JSON.stringify(result.map(row => [row[0], ...row.slice(1).sort()]).sort());
}

const a1 = [
    ["John","johnsmith@mail.com","john_newyork@mail.com"],
    ["John","johnsmith@mail.com","john00@mail.com"],
    ["Mary","mary@mail.com"],
    ["John","johnnybravo@mail.com"],
];
const e1 = [
    ["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],
    ["Mary","mary@mail.com"],
    ["John","johnnybravo@mail.com"],
];
console.assert(normalize(accountsMerge(a1)) === normalize(e1));
console.assert(normalize(accountsMerge([["Alice","a@x.com"]])) === normalize([["Alice","a@x.com"]]));
console.log("all tests pass");

Number of Provinces, Union-Find to count connected components
Graph Valid Tree, Union-Find to detect cycles and single component
Redundant Connection, Union-Find to find the cycle-forming edge

Graph Traversal, visited-state tactics for exploring nodes, edges, components, and reachability relationships.
Union Find, disjoint-set tactics for tracking connected components as edges arrive.

721. Accounts Merge (Medium)

Problem

Try it yourself

Approach: Union-Find on emails

Why union under the first email?

Summary

Test cases

Related topics

Related concepts