Merge Contact Cards

Medium

An address book has piled up duplicates. You are given a list cards: each card starts with a person's name, followed by their email addresses. Two cards belong to the same person if they share at least one address. The link is transitive: if card A overlaps with B and B overlaps with C, all three belong to one person. A matching name alone means nothing, since namesakes can be different people. However, all cards of the same person are guaranteed to carry the same name. Merge the cards and return one per person: the name first, then all of their addresses without repeats, in lexicographic order. The cards themselves may come in any order.

Example 1

cards=[['Anna', '[email protected]', '[email protected]'], ['Boris', '[email protected]'], ['Anna', '[email protected]', '[email protected]'], ['Anna', '[email protected]']] → [['Anna', '[email protected]', '[email protected]', '[email protected]'], ['Boris', '[email protected]'], ['Anna', '[email protected]']]

Anna's first and third cards share [email protected], so they are one person and their addresses are merged and sorted. The fourth Anna shares no address with anyone, so she stays a separate person despite the same name.

Example 2

cards=[['Lee', '[email protected]', '[email protected]'], ['Lee', '[email protected]', '[email protected]'], ['Lee', '[email protected]', '[email protected]']] → [['Lee', '[email protected]', '[email protected]', '[email protected]', '[email protected]']]

The first two cards share nothing directly, but the third links them through [email protected] and [email protected], so all three end up as one.

Example 3

cards=[['Mia', '[email protected]', '[email protected]']] → [['Mia', '[email protected]']]

A repeated address appears only once in the answer.

Constraints

1 ≤ len(cards) ≤ 1000
2 ≤ len(cards[i]) ≤ 10
1 ≤ length of every string ≤ 30
cards[i][0] consists of English letters
The other strings are valid email addresses
Cards that share an address have the same name

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Union Find Array Hash Table String Sorting

Similar problems

Rearrange Through Links Medium Chains of Synonyms Medium One-Swap Word Families Hard Ratio Chain Queries Medium A Board Cut by Slashes Medium

Input

cards=[['Anna', '[email protected]', '[email protected]'], ['Boris', '[email protected]'], ['Anna', '[email protected]', '[email protected]'], ['Anna', '[email protected]']]

Expected

[['Anna', '[email protected]', '[email protected]', '[email protected]'], ['Boris', '[email protected]'], ['Anna', '[email protected]']]

Run checks the first 3 tests in your browser. Submit checks all 58 tests on the server, hidden ones included.