Accounts Merge

▶

Steps

setup

Initialize Union-Find and Data Structures

Create an empty UnionFind instance and an empty dictionary to map emails to names. No emails or unions exist yet.

💡 Initialization sets up the data structures needed to track email groups and their owners.

Line:

uf = UnionFind()
email_to_name = {}

💡 UnionFind starts empty; no parent or rank mappings exist yet.

traverse

Process First Account: John with [e-mail] and [e-mail]

Map both emails to 'John' and union them. '[e-mail]' is the first email, so union is called between it and '[e-mail]' (self) and then with '[e-mail]'.

💡 Union operations connect emails within the same account, building sets of connected emails.

Line:

name = account[0]
first_email = account[1]
for email in account[1:]:
    email_to_name[email] = name
    uf.union(first_email, email)

💡 Emails in the same account are connected, so they belong to the same set.

traverse

Process Second Account: John with [e-mail]

Map '[e-mail]' to 'John' and union it with itself (no change). This email is isolated so far.

💡 Single-email accounts create isolated sets in union-find.

Line:

name = account[0]
first_email = account[1]
for email in account[1:]:
    email_to_name[email] = name
    uf.union(first_email, email)

💡 Isolated emails form their own sets until connected to others.

traverse

Process Third Account: John with [e-mail] and [e-mail]

Map both emails to 'John' and union '[e-mail]' with '[e-mail]'. '[e-mail]' is already connected to '[e-mail]', so this union connects all three emails.

💡 Union-find merges sets when shared emails appear in multiple accounts.

Line:

name = account[0]
first_email = account[1]
for email in account[1:]:
    email_to_name[email] = name
    uf.union(first_email, email)

💡 Shared emails link accounts, merging their email sets.

traverse

Process Fourth Account: Mary with [e-mail]

Map '[e-mail]' to 'Mary' and union it with itself (no change). This email is isolated.

💡 New unique emails form new isolated sets.

Line:

name = account[0]
first_email = account[1]
for email in account[1:]:
    email_to_name[email] = name
    uf.union(first_email, email)

💡 Isolated emails remain separate sets.

prune

Find Root Parents for Each Email

For each email, find its root parent in the union-find structure to identify connected components.

💡 Finding roots groups emails by their connected sets.

Line:

for email in email_to_name:
    root = uf.find(email)
    unions.setdefault(root, []).append(email)

💡 Emails with the same root belong to the same merged account.

prune

Group Emails by Root Parent

Emails are grouped into lists keyed by their root parent email, forming clusters representing merged accounts.

💡 Grouping by root parent collects all connected emails together.

Line:

unions.setdefault(root, []).append(email)

💡 Each group corresponds to one merged account.

fill_cells

Sort Emails in Each Group

Sort the emails in each group alphabetically to prepare for the final merged account output.

💡 Sorting ensures consistent order in the merged accounts.

Line:

merged.append([email_to_name[root]] + sorted(emails))

💡 Sorted emails improve readability and meet problem requirements.

reconstruct

Construct Final Merged Accounts

Combine each group's sorted emails with the corresponding name to form the final merged account lists.

💡 Adding the name completes the merged account representation.

Line:

merged.append([email_to_name[root]] + sorted(emails))

💡 Final output format includes name and sorted emails per merged account.

reconstruct

Return Final Merged Accounts

Return the list of merged accounts as the final answer, showing the combined and sorted emails per user.

💡 Returning the answer completes the algorithm.

Line:

return merged

💡 The algorithm successfully merges accounts sharing emails.

from typing import List

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}

    def find(self, x):
        if x != self.parent.setdefault(x, x):  # STEP 6
            self.parent[x] = self.find(self.parent[x])  # STEP 6
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)  # STEP 2,4
        rootY = self.find(y)  # STEP 2,4
        if rootX != rootY:  # STEP 2,4
            rankX = self.rank.setdefault(rootX, 0)  # STEP 2,4
            rankY = self.rank.setdefault(rootY, 0)  # STEP 2,4
            if rankX < rankY:
                self.parent[rootX] = rootY  # STEP 2,4
            elif rankX > rankY:
                self.parent[rootY] = rootX  # STEP 2,4
            else:
                self.parent[rootY] = rootX  # STEP 2,4
                self.rank[rootX] += 1  # STEP 2,4

def accountsMerge(accounts: List[List[str]]) -> List[List[str]]:
    uf = UnionFind()  # STEP 1
    email_to_name = {}  # STEP 1

    for account in accounts:  # STEP 2-5
        name = account[0]
        first_email = account[1]
        for email in account[1:]:
            email_to_name[email] = name
            uf.union(first_email, email)

    unions = {}  # STEP 6-7
    for email in email_to_name:
        root = uf.find(email)
        unions.setdefault(root, []).append(email)

    merged = []  # STEP 8-9
    for root, emails in unions.items():
        merged.append([email_to_name[root]] + sorted(emails))
    return merged  # STEP 10

📊

Accounts Merge - Watch the Algorithm Execute, Step by Step

Watching the union-find operations and grouping visually reveals how shared emails connect accounts, making the merging logic intuitive and clear.

Visiting: none

Visiting: none

[e-mail]

[e-mail]

Visiting: none

[e-mail]

[e-mail]

[e-mail]

Visiting: none

[e-mail]

[e-mail]

[e-mail]

[e-mail]

Visiting: none

[e-mail]

[e-mail]

[e-mail]

[e-mail]

[e-mail]

Visiting: [e-mail]

[e-mail]

[e-mail]

[e-mail]

[e-mail]

[e-mail]

Queue / Stack

[e-mail]

Visiting: none

[e-mail]

[e-mail]

[e-mail]

[e-mail]

[e-mail]

Visiting: none

[e-mail]

[e-mail]

[e-mail]

[e-mail]

[e-mail]

Visiting: none

John_merged

John_johnnybravo

Mary_merged

Key Takeaways

✓ Union-Find efficiently merges accounts by connecting emails sharing the same root parent.

Without visualization, it's hard to see how union-find groups emails dynamically as accounts are processed.

✓ Shared emails act as bridges linking multiple accounts into one merged group.

Visualizing these connections clarifies why some accounts merge and others remain separate.

✓ Sorting emails after grouping ensures consistent output order, which is critical for correctness.

This step is easy to overlook but essential for matching expected output.

Practice

1. You are given an undirected, weighted graph and need to find a subset of edges that connects all vertices with the minimum possible total edge weight, without forming any cycles. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Dynamic Programming on subsets of edges to find minimum cost spanning subgraph

B. Greedy algorithm sorting edges by weight and using union-find to avoid cycles

C. Depth-First Search to find all spanning trees and pick the minimum weight one

D. Breadth-First Search to find shortest paths and combine them into a spanning tree

Solution

1. Step 1: Understand the problem requirements

   The problem asks for a minimum total edge weight subset connecting all vertices without cycles, which is the definition of a Minimum Spanning Tree (MST).

2. Step 2: Identify the algorithm that guarantees optimal MST efficiently

   Kruskal's algorithm sorts edges by weight and uses union-find to avoid cycles, ensuring minimal total weight and connectivity efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Greedy + union-find is classic MST approach [OK]

Hint: MST needs cycle-free minimal edges; union-find + sorting fits [OK]

Common Mistakes:

• Thinking DFS or BFS can find MST optimally
• Assuming DP on subsets is efficient here
• Believing greedy without cycle checks works

2. Consider the following Python code implementing Union-Find to solve the network connectivity problem. Given n = 4 and connections = [[0,1],[0,2],[1,2]], what is the final return value of makeConnected(n, connections)?

easy

A. -1

B. 1

C. 0

D. 2

Solution

1. Step 1: Check if enough connections exist

   There are 3 connections and 4 nodes, so 3 >= 4-1, proceed.

2. Step 2: Perform unions and count components

   Union(0,1) reduces count from 4 to 3, Union(0,2) reduces count to 2, Union(1,2) finds same root, no change. Final count = 2.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Minimum operations = components - 1 = 2 - 1 = 1 [OK]

Hint: Count after unions minus one equals operations needed [OK]

Common Mistakes:

• Returning count instead of count - 1
• Not checking connection count before union
• Off-by-one in union count decrement

3. You are given a string and a list of index pairs where you can swap characters any number of times. The goal is to find the lexicographically smallest string possible after performing any swaps allowed by these pairs. Which algorithmic approach best guarantees an optimal solution for this problem?

easy

A. Greedy approach that swaps characters whenever a smaller character is found at a connected index

B. Union-Find to group connected indices, then sort characters within each group to reconstruct the smallest string

C. Dynamic programming to try all possible swaps and pick the lexicographically smallest result

D. Breadth-first search to explore all possible strings reachable by swaps and select the smallest

Solution

1. Step 1: Understand problem constraints

   The problem allows unlimited swaps between indices connected by pairs, so indices form connected components.

2. Step 2: Identify approach that groups indices

   Union-Find efficiently groups indices into connected components, enabling sorting characters within each group to get the smallest lexicographic order.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Union-Find groups indices correctly, sorting within groups yields optimal string [OK]

Hint: Group indices first, then sort characters within groups [OK]

Common Mistakes:

• Assuming greedy swaps suffice
• Trying DP over all permutations
• Using BFS to explore all strings exhaustively

4. Examine the following buggy Union-Find code snippet for the network connectivity problem. Which line contains the subtle bug that can cause incorrect results on some inputs?

medium

A. Line with 'return self.find(self.parent[x])' in find method

B. Line 'self.count = n' in __init__ method

C. Line 'self.rank[rootX] += 1' in union method

D. Line 'self.parent[rootX] = rootY' in union method

Solution

1. Step 1: Identify path compression implementation

   The find method should assign the parent during recursion: self.parent[x] = self.find(self.parent[x]) to flatten the tree.

2. Step 2: Understand impact of missing assignment

   Without path compression, find operations become slower and can cause TLE or incorrect component counts on large inputs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing path compression assignment is a classic subtle bug [OK]

Hint: Path compression requires assignment to parent during find [OK]

Common Mistakes:

• Forgetting path compression assignment
• Misplacing rank increment
• Incorrectly decrementing count

5. The following code attempts to implement the optimal solution for the smallest string with swaps problem. Identify the line that contains a subtle bug that can cause incorrect output.

medium

A. Line: for i, idx in enumerate(group): res[idx] = chars[i]

B. Line: groups[uf.find(i)].append(i)

C. Line: for x, y in pairs: uf.union(x, y)

D. Line: chars.sort()

Solution

1. Step 1: Identify grouping and sorting

   Indices in each group are collected but not sorted before assignment.

2. Step 2: Check assignment order

   Assigning sorted characters to unsorted group indices causes characters to be placed incorrectly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting group indices before assignment fixes the bug [OK]

Hint: Always sort indices before assigning sorted chars [OK]

Common Mistakes:

• Not sorting indices before assignment
• Assuming group order matches index order