LeetCode 721 Accounts Merge - Example and Complexity Analysis

Trace [["John","a@m","b@m"],["John","b@m","c@m"],["Mary","d@m"]].

Process account 0: union(a@m, b@m). Components: {a@m, b@m}, {c@m}, {d@m}.

Process account 1: union(b@m, c@m). Now a@m, b@m, c@m share a root. Components: {a@m, b@m, c@m}, {d@m}.

Process account 2: d@m stays alone.

Group by root: {a@m, b@m, c@m} → "John", {d@m} → "Mary".

Sort emails within each group. Output: [["John","a@m","b@m","c@m"],["Mary","d@m"]].

$O(E \cdot \alpha(E))$ for union-find where $E$ is total emails. $O(E \log E)$ for sorting. $O(E)$ space.