Warning: This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#721) before relying on it.

Accounts Merge

An interactive visualization of the Union-Find approach to merging accounts. Watch how shared emails connect accounts into groups, then see the merged results.

Union-Find LeetCode 721 ↗ Medium

The Problem

Given a list of accounts where each element accounts[i] is a list of strings, the first element accounts[i][0] is a name, and the rest are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. After merging, return the accounts in the format: the first element is the name, and the rest are emails in sorted order.

Note: Even if two accounts have the same name, they may belong to different people. A person can have any number of accounts initially, but all of their accounts have the same name.

Interactive Visualization

Accounts (JSON format)

Preset

Speed:

Accounts

Union-Find State

parent { }

Empty

email_to_name { }

Empty

Merged Result

Code

fun accountsMerge(accounts: List<List<String>>): List<List<String>> {    val parent = mutableMapOf<String, String>()    fun find(x: String): String { var node = x        while (parent[node] != node) {            parent[node] = parent[parent[node]!!]!!            node = parent[node]!! }        return node }    fun union(x: String, y: String) {        val px = find(x); val py = find(y)        if (px != py) parent[px] = py }    val emailToName = mutableMapOf<String, String>()    for (account in accounts) {        val name = account[0]; val emails = account.drop(1)        for (email in emails) { if (email !in parent)            parent[email] = email        emailToName[email] = name        union(emails[0], email) } }    val groups = mutableMapOf<String, MutableList<String>>()    for (email in parent.keys) {        val root = find(email)        groups.getOrPut(root) { mutableListOf() }.add(email)    }    return groups.map { (root, emails) ->        listOf(emailToName[root]!!) + emails.sorted() } }

def accountsMerge(accounts):    parent = {}    def find(x):        while parent[x] != x:            parent[x] = parent[parent[x]]            x = parent[x]        return x    def union(x, y):        px, py = find(x), find(y)        if px != py:            parent[px] = py    email_to_name = {}    for name, *emails in accounts:        for email in emails:            if email not in parent:                parent[email] = email            email_to_name[email] = name            union(emails[0], email)    groups = {}    for email in parent:        root = find(email)        groups.setdefault(root, []).append(email)    return [[email_to_name[root]] + sorted(emails)            for root, emails in groups.items()]

Current Step

Press Step or Play to begin.

How It Works

Key Insight

Two accounts belong to the same person if they share any email address. This is a connectivity problem -- we need to find connected components where edges are defined by shared emails. Union-Find (Disjoint Set Union) is the perfect data structure for this.

The Algorithm

Initialize an empty parent dictionary for Union-Find and an email_to_name mapping.
For each account, iterate through its emails:
-- If the email is new, initialize its parent to itself.
-- Map the email to the account name.
-- union(emails[0], email) -- union the first email of this account with every other email in the account.
Collect groups: For every email, find its root and group emails by root.
Build result: For each group, output [name] + sorted(emails).

The key trick is that within each account, we union all emails with the first email. If two accounts share an email, that shared email links both accounts' first emails together transitively.

Complexity

Time O(N * K * alpha(N*K))

Space O(N * K)

Where N is the number of accounts and K is the maximum number of emails per account. The alpha factor is the inverse Ackermann function from Union-Find with path compression, which is effectively O(1) for all practical inputs. Sorting the final groups adds O(NK log(NK)).