Unique Email Groups - Solution & Explanation

Problem Overview: You receive a list of email addresses and must determine how many unique groups exist after applying normalization rules. Typically the local part of the email may ignore characters like . or discard everything after +, while the domain remains unchanged. Different raw strings can represent the same effective email, so the goal is to normalize each address and count distinct results.

Approach 1: Brute Force Normalization with List Comparison (O(n² · m) time, O(n · m) space)

Process each email and convert it into its normalized form using basic string operations. Remove dots in the local part and ignore characters after the first +, then append the unchanged domain. Instead of using a hash structure, store normalized results in a list and check each new email against all previous entries to see if it already exists. Each comparison may scan the string, giving O(m) cost per comparison, and up to n comparisons per email. This approach works for small inputs but becomes inefficient when the list grows.

Approach 2: Hash Table for Unique Normalized Emails (O(n · m) time, O(n · m) space)

The efficient solution uses a hash table (or hash set) to track normalized email addresses. Iterate through the array of emails once. For each email, split it into local and domain parts using the @ separator. Scan the local part character by character: skip ., stop when encountering +, and keep the remaining characters. Reconstruct the normalized email as processedLocal + "@" + domain. Insert the result into a hash set; duplicates are automatically ignored due to constant-time hash lookups.

The key insight is that normalization guarantees that all equivalent emails map to the same canonical string. A hash set makes duplicate detection constant time on average, reducing the overall complexity to O(n · m), where n is the number of emails and m is the average length of an email string.

Recommended for interviews: The hash table approach is what interviewers expect. It demonstrates that you can combine string parsing with constant‑time hash lookups to deduplicate data efficiently. Mentioning the brute force approach first shows you understand the baseline solution, but implementing the hash set version proves you can optimize both time complexity and code clarity.