MediumNeetCode150Depth-First SearchBreadth-First SearchUnion FindGraph
Accounts Merge
Merge accounts sharing common emails.
Examples
Input
accounts = [[John,john@abc.com,john1@abc.com],[John,john@abc.com,john2@abc.com],[Mary,mary@abc.com]]
Output
[[John,john@abc.com,john1@abc.com,john2@abc.com],[Mary,mary@abc.com]]
Merged John's accounts.
Constraints
- •
1 <= accounts.length <= 1000 - •
2 <= accounts[i].length <= 10 - •
1 <= accounts[i][j].length <= 30
Approaches
Build graph, DFS.
CodeT: O(N*K*logK) | S: O(N*K)
Union emails, group by root.
CodeT: O(N*K*logK) | S: O(N*K)
Same approach.
CodeT: O(N*K) | S: O(N*K)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| DFS | O(N*K*logK) | O(N*K) | Build graph, DFS. |
| Union Find | O(N*K*logK) | O(N*K) | Union emails, group by root. |
| Union Find + Map | O(N*K) | O(N*K) | Same approach. |
DFS
T: O(N*K*logK)S: O(N*K)
Build graph, DFS.
Union Find
T: O(N*K*logK)S: O(N*K)
Union emails, group by root.
Union Find + Map
T: O(N*K)S: O(N*K)
Same approach.
Common Mistakes
Not handling multiple accounts
Wrong union-find implementation
Not sorting emails