Optimizing with Sets: Membership & Deduplication

What is a Set?

A set is a collection with two defining properties:

1. Unique Elements: It cannot contain duplicate items.
2. Unordered: The elements are not stored in any particular sequence. This means you cannot access elements by an index like you do with a list (e.g., my_set[0] is not possible).

Let's watch a short video to see these properties in action and understand how sets differ from lists.

As the video showed, you can create a set using curly braces {} or the set() constructor.

# Creating a set with curly braces
s1 = {1, 2, 3, 4, 3, 2} 
print(s1)  # Output: {1, 2, 3, 4} - duplicates are automatically removed

# Creating a set from a list
my_list = ['apple', 'banana', 'apple']
s2 = set(my_list)
print(s2)  # Output: {'banana', 'apple'} - order is not guaranteed

# Creating an empty set (IMPORTANT!)
empty_set = set()
# not_a_set = {} # This creates an empty DICTIONARY, not a set.

Now let's explore the two primary use cases where sets give you a massive performance boost.

Use Case 1: Removing Duplicates

The most direct application of a set's "unique elements" property is to de-duplicate a list. The method is simple and elegant: convert the list to a set, and then back to a list.

numbers = [1, 5, 2, 8, 5, 10, 2, 11]

# The one-liner to remove duplicates
unique_numbers = list(set(numbers))

print(unique_numbers) # Output might be [1, 2, 5, 8, 10, 11] (order is not preserved)

This is the standard, most Pythonic way to get unique elements from a sequence. For a more detailed look, including a performance comparison against a less efficient method, the following article is helpful.

Use Case 2: Efficient Membership Testing

This is where your knowledge of complexity analysis comes into play. A very common task is to check if an item exists within a collection of items.

Consider this problem: "Given a large list of user IDs, quickly check if a specific user ID is present."

With a List:
If you use a list, the in operator performs a linear search. It checks the first element, then the second, and so on, until it finds a match or reaches the end.

user_ids_list = [101, 204, 305, ..., 99999]
# To check `if 99999 in user_ids_list:`, Python may have to look at every single element.

From our last lesson, you know this is an O(n) operation. For a list with a million items, this could mean a million comparisons in the worst case.

With a Set:
Sets are implemented using a data structure called a hash table. The details of hash tables are a topic for another day, but the practical consequence is extraordinary: checking for an element's existence is, on average, a constant time operation.

That's right, it's O(1).

It doesn't matter if the set has 10 elements or 10 million; the time it takes to find an item is roughly the same. This is because the hash of the element tells Python almost exactly where to look, so it doesn't need to search the whole collection.

Let's connect this directly to a coding problem.

From O(n²) to O(n): A Practical Example

Imagine you need to write a function has_duplicates(items) that returns True if a list contains any duplicate values.

A straightforward approach might look like this:

# The INEFFICIENT approach
def has_duplicates_list(items):
    seen = [] # Use a list to store items we've seen
    for item in items:
        if item in seen: # This 'in' check is O(k), where k is the current size of 'seen'
            return True
        seen.append(item)
    return False

Can you analyze the complexity? The outer loop runs n times. Inside the loop, item in seen is a linear search on the seen list, which grows up to size n. This combination of a loop with a linear search inside it results in a total time complexity of O(n²). This will be too slow for large inputs in competitive programming.

Now, let's use a set.

# The EFFICIENT approach
def has_duplicates_set(items):
    seen = set() # Use a set to store items we've seen
    for item in items:
        if item in seen: # This 'in' check is O(1) on average!
            return True
        seen.add(item)
    return False

Here, the outer loop still runs n times. But the check item in seen is now O(1). The total time complexity is n * O(1), which is simply O(n). You've just improved the algorithm's efficiency quadratically!

This exact optimization is detailed in the following article.

Essential Set Methods: add, remove, discard

Besides membership testing, you'll often need to modify a set.

• .add(element): Adds an element to the set. If the element is already there, it does nothing. (O(1) on average)
• .remove(element): Removes an element. If the element is not in the set, it raises a KeyError. (O(1) on average)
• .discard(element): Removes an element. If the element is not in the set, it does nothing. This is safer than .remove() if you're not sure the element exists. (O(1) on average)

This video segment explains these methods clearly.

def count_common_elements(list_a, list_b):
    # Convert one list to a set for O(1) lookups.
    # The size of the set will be at most len(list_a).
    # This step takes O(len(list_a)) time.
    set_a = set(list_a)
    
    common_count = 0
    # Iterate through the second list. This takes O(len(list_b)) time.
    for element in list_b:
        # Membership check in a set is O(1) on average.
        if element in set_a:
            common_count += 1
            # To be even more efficient and handle duplicates in list_b correctly,
            # we can remove the element from the set after finding it.
            set_a.remove(element)
            
    return common_count

Conclusion

You've now added a fundamental tool to your competitive programming arsenal. Choosing the right data structure is just as important as choosing the right algorithm, and the set is often the key to an optimal solution.

Key Takeaways:

• Sets are unordered collections of unique elements.
• They provide a simple and fast way to remove duplicates from a list: list(set(my_list)).
• The primary advantage of sets is their O(1) average time complexity for membership testing (in), adding (.add), and removing (.remove/.discard).
• Always consider using a set when you need to frequently check for the existence of an item or track seen items in a problem.

Up Next:

In our next lesson, we will explore another core Python data structure: the tuple. We'll focus on its property of immutability (being unchangeable) and see why this characteristic is important, especially since sets require their elements to be immutable.