Group duplicate records that share any property

You are given a list of records. Each record has a unique integer ID and three properties, for example a name, an email and a phone number:

(id, prop1, prop2, prop3)

Two records are duplicates when they hold the same value in the same property. Duplication is transitive: if record A matches B on one property and B matches C on another, then A, B and C all belong to one group, even if A and C share nothing.

Implement:

def group_records(records: list[tuple[int, str | None, str | None, str | None]]) -> list[list[int]]

Return every group as a sorted list of IDs. Order the groups by their smallest ID. A record with no matches forms a group by itself. A missing value (None or an empty string) never matches anything. A value in one property does not match the same value in a different property.

Constraints: up to 10^5 records. Aim for better than comparing every pair.

Example 1

records = [
  (1, "ana", "ana@x.io", "555-01"),
  (2, "ben", "ben@x.io", "555-02"),
  (3, "cy",  "ana@x.io", "555-03"),
  (4, "dee", "dee@x.io", "555-02"),
  (5, "eli", "eli@x.io", "555-05"),
]
output: [[1, 3], [2, 4], [5]]

Records 1 and 3 share an email. Records 2 and 4 share a phone.

Example 2

records = [
  (10, "a", "m1", "p1"),
  (11, "b", "m1", "p2"),
  (12, "c", "m2", "p2"),
  (13, "c", "m3", "p3"),
]
output: [[10, 11, 12, 13]]

10 links to 11 by email, 11 to 12 by phone, and 12 to 13 by name.

Reconstructed from the reported question; details may differ from what interviewers ask.