Union-Find for Entity Merging

In our last lesson, we saw how Union-Find can be used to detect redundant connections by identifying when an edge attempts to connect two nodes that are already part of the same component. This application focused on what happens when a union operation fails. Today, we pivot to a different, equally powerful application that focuses on the end result of successful union operations: grouping related items.

This lesson addresses the learning outcome: Apply Union-Find to solve entity merging problems, such as 'Accounts Merge'. We will tackle the classic LeetCode problem 'Accounts Merge', which involves consolidating user accounts based on shared email addresses. This pattern is incredibly useful for problems involving data cleaning, deduplication, and identifying connected entities in datasets that aren't explicitly represented as graphs.

The Problem: Merging Accounts

Imagine you are given a list of user accounts. Each account contains a name and one or more email addresses. The rule is simple: if two accounts share even a single email address, they belong to the same person and must be merged. This property is transitive—if account A shares an email with B, and B shares a different email with C, then all three accounts (A, B, and C) belong to the same person.

The goal is to produce a final list of merged accounts. Each merged account should contain the person's name and a single, sorted list of all unique emails belonging to that person.

For example:
[["John", "a@mail.com"], ["John", "b@mail.com", "a@mail.com"], ["Mary", "c@mail.com"]]

Here, the first two "John" accounts share a@mail.com. They must be merged. The final output should be:
[["John", "a@mail.com", "b@mail.com"], ["Mary", "c@mail.com"]]

This problem of finding and merging connected components is a perfect fit for the Union-Find data structure.

The Union-Find Strategy for Merging

The core challenge is translating this problem into a format that Union-Find can solve. We need to define what our "elements" are and what "connecting" them means.

1. The Elements: The entities we are merging are the accounts themselves. We can identify each account by its index in the initial input list. If we have N accounts, we will initialize a Union-Find data structure for N elements, 0 to N-1.

2. The Connection: The connection between accounts is a shared email. The key insight is to use a hash map to track which account an email belongs to.

The overall algorithm consists of two main passes:

Pass 1: Union Accounts Based on Shared Emails

We iterate through each account and its emails. We'll use a hash map, let's call it email_to_account_index, to store the first account index we see associated with each email.

For each (account_index, emails) pair:

• For each email in emails:
  • If the email is already in our email_to_account_index map, it means we've seen this email before in a different account. Let the previously seen account index be prev_index = email_to_account_index[email]. This shared email tells us that account_index and prev_index belong to the same person. We perform union(account_index, prev_index).
  • If the email is not in the map, this is the first time we're seeing it. We record its origin: email_to_account_index[email] = account_index.

After this pass, our Union-Find structure has grouped all connected accounts into disjoint sets.

Pass 2: Consolidate Emails into Merged Groups

Now that the accounts are grouped, we need to collect all the emails for each group.

• Create a new map, let's call it root_to_emails. This map will associate the root of each disjoint set with a collection of all emails belonging to that group. A defaultdict(set) in Python is perfect, as the set will automatically handle duplicate emails.
• Iterate through the email_to_account_index map we built earlier. For each (email, account_index) pair:
  • Find the ultimate parent of the account: root = find(account_index).
  • Add the email to the set for that root: root_to_emails[root].add(email).

After this pass, root_to_emails contains the complete, deduplicated list of emails for each merged entity, identified by its root account index.

Pass 3: Format the Final Output

The last step is to build the result in the required format.

• Iterate through the root_to_emails map. For each (root_index, email_set) pair:
  • Retrieve the name from the original input list: name = accounts[root_index][0].
  • Convert the email_set to a list and sort it alphabetically.
  • Create the final merged account: [name] + sorted_emails.
  • Append this to your final results list.

Guided Explanations and Walkthroughs

To see this process in action, the following resources provide excellent visual and textual explanations.

This video from NeetCodeIO provides a concise walkthrough of the intuition and a clear Python implementation.

For a more detailed, step-by-step trace of how the data structures change, the "take U forward" video is also highly recommended.

Implementation Details and Common Pitfalls

The logic is intricate, and a solid written reference is invaluable. The Algo.monster article provides an excellent breakdown of the solution.

The standard UnionFind class with path compression and union by size/rank remains the same as in previous lessons. The main logic for this specific problem orchestrates the calls to union and find as described.

# Assuming a standard UnionFind class is defined elsewhere

def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
    uf = UnionFind(len(accounts))
    email_to_account_index = {} # email -> account_idx




    # Pass 1: Union accounts with common emails
    for i, acc in enumerate(accounts):
        for email in acc[1:]:
            if email in email_to_account_index:



                # This email has been seen before, union the accounts
                uf.union(i, email_to_account_index[email])
            else:



                # First time seeing this email, map it to this account index
                email_to_account_index[email] = i




    # Pass 2: Group emails by their root account
    root_to_emails = defaultdict(set)
    for i, acc in enumerate(accounts):
        root = uf.find(i)



        # Add all emails from the current account to the root's set
        root_to_emails[root].update(acc[1:])




    # Pass 3: Format the final result
    result = []
    for root_idx, emails in root_to_emails.items():
        name = accounts[root_idx][0]



        # Prepend the name to the sorted list of unique emails
        merged_account = [name] + sorted(list(emails))
        result.append(merged_account)
        
    return result

Complexity Analysis

Let N be the number of accounts and E be the total number of email addresses across all accounts.

• Time Complexity: O(E * α(N) + E log E).
  • The first pass involves iterating through all E emails and performing a union operation for each, which takes amortized O(α(N)) time. This gives O(E * α(N)).
  • The second pass also iterates through accounts and their emails.
  • The third pass involves sorting the emails for each merged component. In the worst case, all emails belong to one person, so sorting takes O(E log E).
  • The dominant term is typically the sorting step.
• Space Complexity: O(E + N).
  • We need O(N) space for the Union-Find data structure's parent and size arrays.
  • The email_to_account_index map can store up to E unique emails.
  • The root_to_emails map also stores all E emails in the worst case.

Conclusion

In this lesson, we've extended our understanding of Union-Find beyond simple cycle detection to a powerful pattern for entity merging and data consolidation. By cleverly mapping non-numeric entities (emails) to numeric indices (accounts), we were able to leverage the full power of the Disjoint Set Union data structure to efficiently group related accounts.

Key Takeaways:

• Pattern: Many problems involving merging or grouping items based on shared attributes can be solved with Union-Find.
• Key Technique: Use a hash map to create a bridge between the problem's entities (e.g., emails) and the integer elements that Union-Find operates on (e.g., account indices).
• Two-Pass Approach: A common structure for these problems is a first pass to perform the union operations and a second pass to use the find operation to aggregate the results under their component leaders.

This marks the end of our module on Union-Find. In the next module, we will dive into classic graph algorithms. We'll start with Minimum Spanning Trees (MSTs) and shortest path algorithms. You'll find that one of the most elegant algorithms for finding an MST, Kruskal's algorithm, uses Union-Find at its core to efficiently detect cycles, tying our current topic directly to what comes next.