Hash Sets: Duplicate Detection & Membership Testing

1. What is a Hash Set?

A hash set is a data structure that stores a collection of unique items. Think of it as a hash map where you only care about the keys, not the values. Its primary purpose is to answer one question extremely quickly: "Is this item in the collection?"

The three main operations on a hash set are:

• Add: Adds an item to the set. If the item is already there, nothing changes.
• Contains: Checks if an item exists in the set.
• Remove: Deletes an item from the set.

Because hash sets are built on top of hash tables, these operations have an average time complexity of O(1).

How do Hash Sets achieve O(1) speed?

The "magic" of O(1) average time complexity comes from the underlying hash table. To build your intuition, it's helpful to see how one works under the hood. When you add an item, the set:

1. Computes a hash code for the item (an integer).
2. Uses this hash code to calculate an index into an underlying array.
3. Stores the item at that index.

When you check if an item is in the set, it repeats steps 1 and 2 to instantly find the correct index and see if the item is there, without needing to scan the entire collection.

A key requirement for an object to be stored in a hash set is that it must be hashable, meaning its value cannot change. This is why you can add an integer, string, or tuple to a Python set, but you cannot add a list or dictionary, as they are mutable.

2. Application: The "Contains Duplicate" Problem

Now, let's apply this knowledge to a classic interview question that perfectly illustrates the power of hash sets: Contains Duplicate (LeetCode 217).

Problem Statement: Given an integer array nums, return true if any value appears at least twice in the array, and false if every element is distinct.

Example 1:

• Input: nums = [1, 2, 3, 1]
• Output: true (because 1 appears twice)

Example 2:

• Input: nums = [1, 2, 3, 4]
• Output: false

From Brute-Force to Optimal

As always, let's consider the straightforward approaches first to understand the tradeoffs.

The brute-force and sorting solutions are valid, but we can achieve a linear time solution by using a hash set to keep track of the numbers we've seen.

The algorithm is simple:

1. Initialize an empty hash set, let's call it seen.
2. Iterate through each number n in the input array nums.
3. For each n, check if n is already in seen.
   • If it is, we've found a duplicate. Return true.
   • If it's not, add n to seen to mark that we've now encountered it.
4. If we finish the loop without finding any duplicates, it means all elements were unique. Return false.

Here's the Python code for this approach:

def contains_duplicate(nums: list[int]) -> bool:
    seen = set()  # Initialize an empty hash set
    for n in nums:
        if n in seen:
            return True
        seen.add(n)
    return False

• Time Complexity: $O(n)$. We iterate through the array once. Each add and in operation on the set is $O(1)$ on average.
• Space Complexity: $O(n)$. In the worst case (no duplicates), the set will grow to store all n elements from the input array.

This is another classic time-space tradeoff. We use extra memory to achieve a faster, linear-time algorithm.

The "Pythonic" Shortcut

Python's set type is so convenient that it allows for an elegant one-liner to solve this problem. Since a set can only contain unique elements, if you convert a list to a set, any duplicates are automatically removed.

The logic is: if the length of the set is less than the length of the original list, it must be because duplicates were removed.

def contains_duplicate_oneliner(nums: list[int]) -> bool:
    return len(set(nums)) < len(nums)

This single line of code also has $O(n)$ time complexity (to build the set) and $O(n)$ space complexity (to store the set).

3. Performance in Context

The reason we choose a hash set for duplicate detection and membership testing is its unmatched average-case performance. Other data structures could do the job, but less efficiently. For example, a sorted data structure (like a balanced binary search tree, which backs Java's TreeSet) could also check for membership, but it would take $O(\log n)$ time.

When an interview problem asks you to check for duplicates or manage a collection of unique items without needing them to be ordered, your first thought should be a hash set.

Conclusion

You have now added another essential hash-based pattern to your toolkit. While hash maps are for associating keys with values, hash sets are for managing collections of unique items.

Key Takeaways:

• Hash Sets Store Unique Items: They are designed to enforce uniqueness and provide extremely fast operations.
• O(1) Operations: Adding, removing, and checking for an item in a hash set are all $O(1)$ on average.
• Ideal for Duplicate Detection: The "Contains Duplicate" problem is the canonical example of using a hash set to track seen elements.
• Time-Space Tradeoff: The optimal $O(n)$ time solution requires $O(n)$ space, which is a common and acceptable tradeoff in interviews.

In our next lesson, we will continue exploring problems that can be solved with hashing. We'll focus on anagram and character-based problems, where you'll use hash maps to efficiently count character frequencies, combining ideas from our last two lessons.