Group Fraud Accounts by Shared Signals (Union-Find)

Problem Statement

A fraud detection system flags accounts that share signals. Each account has a list of identifiers — email, phone, device ID. Two accounts belong to the same fraud ring if they share at least one identifier (directly or transitively).

Given a list of accounts (each with a set of identifiers), group them into fraud rings. Return the number of distinct rings and optionally the grouping.

Transitivity matters: if A shares an email with B, and B shares a phone with C, then A, B, and C are all in the same ring — even if A and C share nothing directly.

Constraints

• 1 <= accounts.length <= 10^5
• Each account has 1 to 10 identifiers (strings)
• Identifiers are shared across accounts to form rings
• Aim for near-linear time

Example

Input:

account 0: {email: "a@x.com", phone: "111"}
account 1: {phone: "111", device: "D1"}
account 2: {email: "z@x.com"}
account 3: {device: "D1"}

Output: 2 rings

Explanation: Accounts 0, 1, 3 are linked (0-1 via phone 111, 1-3 via device D1). Account 2 is alone. → 2 rings.

The Insight — Union-Find on Identifiers

The transitive "same ring" relationship screams Union-Find (Disjoint Set Union). The clever part is HOW you union.

The trick — map each identifier to the first account that used it:

1. Maintain a map: identifier → accountId.
2. For each account, for each of its identifiers:
   • If the identifier was seen before, union the current account with the account that first claimed it.
   • Otherwise, record this account as the owner of that identifier.
3. At the end, count distinct roots → number of fraud rings.

This handles transitivity automatically — that's the magic of Union-Find. You never explicitly build the "A→B→C" chain; the union operations with path compression collapse everything into one set. Near O(n·α(n)) time.

The "aha": you don't union accounts directly by comparing every pair (O(n²)). You union through the shared identifier, using the identifier map as the bridge.

Follow-ups

1. Why is unioning through the identifier map far better than comparing all account pairs?
2. How does path compression + union by rank keep this near-linear?
3. How would you also return the SIZE of the largest fraud ring?
4. What if identifiers could expire (time-windowed fraud rings)? How would you handle deletions? (DSU doesn't support easy deletion — discuss alternatives)