Accounts Merge
The drill: Each account lists an owner's name and the emails they signed up with. The same person can show up as several accounts sharing at least one email — merge every account into one per real person, name plus every distinct email, sorted.
A list of accounts arrives, each one holding an owner's name followed by every email address registered under that account. The same real person can show up as multiple separate accounts, connected by sharing at least one email in common.
Two accounts belong to the same person exactly when their email lists overlap — directly, or through a chain of other accounts bridging them together. The name on an account can't be trusted alone, since two different real people might share the same printed name.
The task is to merge every account into one per actual person: that person's name, followed by every distinct email they've ever used, sorted alphabetically. The merged accounts themselves can come back in any order.
- up to a few thousand accounts and emails combined
- two accounts merge whenever they share at least one email
- each merged account lists its emails sorted alphabetically
- order of the merged accounts in the result doesn't matter
HINT 1 THE NUDGE
Two accounts belong to the same person exactly when they share at least one email — the name printed on the account can't be trusted alone, since two different people can share a name.
HINT 2 THE STRUCTURE
Think of every email as a node, and each account as a set of edges tying its emails together. Merging accounts is really finding which emails end up in the same connected cluster.
HINT 3 ONE STEP FROM THE ANSWER
Union every pair of emails inside the same account. Afterward, group all emails by their root, attach whichever account's name owns that root, sort each group's emails, and that's one merged account.
3 accounts arrive: two labeled John share email j1, one labeled Mary stands alone. Union each account's emails against its first email.
class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
parent = {}
owner = {}
def find(x):
parent.setdefault(x, x)
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
for acc in accounts:
name = acc[0]
first = acc[1]
for email in acc[1:]:
owner[email] = name
union(first, email)
groups = collections.defaultdict(list)
for email in owner:
groups[find(email)].append(email)
return [[owner[root]] + sorted(emails) for root, emails in groups.items()]class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
groups = [(acc[0], set(acc[1:])) for acc in accounts]
changed = True
while changed:
changed = False
merged = []
used = [False] * len(groups)
for i in range(len(groups)):
if used[i]:
continue
used[i] = True
name_i, emails_i = groups[i]
for j in range(i + 1, len(groups)):
if used[j]:
continue
name_j, emails_j = groups[j]
if emails_i & emails_j:
emails_i = emails_i | emails_j
used[j] = True
changed = True
merged.append((name_i, emails_i))
groups = merged
return [[name] + sorted(emails) for name, emails in groups]class Solution {
private final Map<String, String> parent = new HashMap<>();
private final Map<String, String> owner = new HashMap<>();
public List<List<String>> accountsMerge(String[][] accounts) {
parent.clear();
owner.clear();
for (String[] acc : accounts) {
String name = acc[0];
String first = acc[1];
for (int i = 1; i < acc.length; i++) {
String email = acc[i];
owner.put(email, name);
union(first, email);
}
}
Map<String, List<String>> groups = new LinkedHashMap<>();
for (String email : owner.keySet()) {
groups.computeIfAbsent(find(email), k -> new ArrayList<>()).add(email);
}
List<List<String>> result = new ArrayList<>();
for (Map.Entry<String, List<String>> e : groups.entrySet()) {
List<String> emails = e.getValue();
Collections.sort(emails);
List<String> row = new ArrayList<>();
row.add(owner.get(e.getKey()));
row.addAll(emails);
result.add(row);
}
return result;
}
private String find(String x) {
parent.putIfAbsent(x, x);
while (!parent.get(x).equals(x)) {
parent.put(x, parent.get(parent.get(x)));
x = parent.get(x);
}
return x;
}
private void union(String a, String b) {
String ra = find(a), rb = find(b);
if (!ra.equals(rb)) parent.put(ra, rb);
}
}class Solution {
public List<List<String>> accountsMerge(String[][] accounts) {
List<String> names = new ArrayList<>();
List<Set<String>> groups = new ArrayList<>();
for (String[] acc : accounts) {
names.add(acc[0]);
groups.add(new HashSet<>(Arrays.asList(acc).subList(1, acc.length)));
}
boolean changed = true;
while (changed) {
changed = false;
List<String> mergedNames = new ArrayList<>();
List<Set<String>> mergedGroups = new ArrayList<>();
boolean[] used = new boolean[groups.size()];
for (int i = 0; i < groups.size(); i++) {
if (used[i]) continue;
used[i] = true;
Set<String> emailsI = groups.get(i);
for (int j = i + 1; j < groups.size(); j++) {
if (used[j]) continue;
Set<String> emailsJ = groups.get(j);
if (!Collections.disjoint(emailsI, emailsJ)) {
emailsI.addAll(emailsJ);
used[j] = true;
changed = true;
}
}
mergedNames.add(names.get(i));
mergedGroups.add(emailsI);
}
names = mergedNames;
groups = mergedGroups;
}
List<List<String>> result = new ArrayList<>();
for (int i = 0; i < groups.size(); i++) {
List<String> emails = new ArrayList<>(groups.get(i));
Collections.sort(emails);
List<String> row = new ArrayList<>();
row.add(names.get(i));
row.addAll(emails);
result.add(row);
}
return result;
}
}✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED