Merge Customer Records

MediumGraphs

Problem

A CRM export contains records. Each record is [name, email1, email2, ...] with at least one email. Two records belong to the same customer if they share any email, directly or through a chain of records. Records of the same customer always carry the same name, but different customers may share a name.

Merge the records and return one entry per customer: [name, ...emails] with that customer's distinct emails sorted ascending. Order the entries by their first (smallest) email.

Example 1

Input:
records = [["Ana", "ana@x.io", "a.r@y.com"], ["Ben", "ben@z.org"], ["Ana", "a.r@y.com", "ana.r@w.net"]]
Output:
[["Ana", "a.r@y.com", "ana.r@w.net", "ana@x.io"], ["Ben", "ben@z.org"]]

The two Ana records share a.r@y.com. Strings compare character by character, and '.' sorts before '@'.

Example 2

Input:
records = [["Kai", "k1@m.com"], ["Kai", "k2@m.com"]]
Output:
[["Kai", "k1@m.com"], ["Kai", "k2@m.com"]]

Same name, no shared email: two customers.

Example 3

Input:
records = [["Lu", "c@q.com", "d@q.com"], ["Lu", "a@q.com", "b@q.com"], ["Lu", "b@q.com", "c@q.com"]]
Output:
[["Lu", "a@q.com", "b@q.com", "c@q.com", "d@q.com"]]

The third record links the first two.

Constraints

  • 1 ≤ records.length ≤ 1000
  • 2 ≤ records[i].length ≤ 10
  • Emails are lowercase ASCII, length ≤ 30.

Hint

Show the first hint

Think of emails as nodes. What does a single record tell you about its emails?

Walkthrough

How to approach it

01Clarify before coding

  • Is the name enough to merge two records? No, only a shared email links records.
  • Can one record list the same email twice? Yes; each email appears once in the output.
  • How are customers ordered? By their smallest email, using plain character-by-character comparison.

02Brute force

Repeatedly scan all pairs of groups, merging any two that share an email, until a full pass merges nothing.

Cost: Each pass is O(r²·k) for r records of k emails, and up to r passes are needed: O(r³·k), about 10^10 for 1000 records.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.