Report Spam Message - Solution & Explanation

Problem Overview: You receive a message represented as an array of words and another list containing banned words. The task is to determine whether the message should be reported as spam. A message is considered spam if at least two words from the message appear in the banned list.

Approach 1: Hash Set for Fast Lookup (O(n + m) time, O(m) space)

The most practical solution converts the banned word list into a hash set. This gives constant-time membership checks. First iterate through the banned array and insert each word into the set. Then iterate through the message words and check whether each word exists in the set using a hash lookup. Maintain a counter for matches and stop once the count reaches two.

The key insight is that repeated membership checks become expensive if the banned list is scanned each time. A hash set reduces that lookup from O(m) to O(1). The total complexity becomes O(n + m), where n is the number of words in the message and m is the size of the banned list. Space complexity is O(m) for the set. This pattern appears frequently in problems involving fast membership checks on hash tables and word matching across arrays.

Approach 2: Frequency Count with Early Exit (O(n + m) time, O(m) space)

Another way is to track occurrences of banned words using a frequency structure. Build a hash map or set from the banned list, then iterate through the message while counting matches. As soon as the second banned word is encountered, immediately return true. This early exit avoids scanning the entire message when spam is detected early.

This approach behaves similarly to the hash set strategy but emphasizes counting and early termination. The algorithm still performs a single pass through the message with constant-time lookups. Time complexity remains O(n + m), and space complexity stays O(m). Early termination often improves real-world performance when spam appears near the beginning of the message.

Both solutions rely on efficient word comparison and are common in moderation or filtering systems where strings must be matched against restricted lists. Problems involving string matching and hash-based membership checks frequently use this exact design.

Recommended for interviews: The hash set lookup approach is what most interviewers expect. It demonstrates that you recognize repeated membership checks and optimize them with a hash-based structure. Mentioning the naive scan and then replacing it with a set shows clear reasoning. Implementing the early exit variant further shows attention to practical performance.