Medium · Hash Maps

Remove duplicate contacts

Given a list of contacts, each with a unique ID and a list of emails, where two contacts are the same person if they share an email directly or through a chain of shared emails, return one contact per person: for each group, in the order of its first contact, return the group's last contact in input order, unchanged.

Examples

Example 1

{
  "contacts": [
    {"id": 1, "emails": ["a@x", "b@x"]},
    {"id": 2, "emails": ["b@x"]},
    {"id": 3, "emails": ["c@x"]},
    {"id": 4, "emails": ["c@x", "d@x"]}
  ]
}

Output: [{ID 2, Emails [b@x]}, {ID 4, Emails [c@x, d@x]}]

Example 2

{
  "contacts": [
    {"id": 1, "emails": ["p@x"]},
    {"id": 2, "emails": ["q@x"]},
    {"id": 3, "emails": ["r@x"]}
  ]
}

Output: [{ID 1, Emails [p@x]}, {ID 2, Emails [q@x]}, {ID 3, Emails [r@x]}]

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.