Solving Problems with Python Sets

The Basics: Working with Sets in Python

Let's begin by learning the fundamental syntax for creating sets, adding or removing items, and checking their contents.

To summarize the key points from the video:

• Creating a set: You can create a set by passing an iterable (like a list) to the set() constructor, or by placing comma-separated items inside curly braces {}.
• Uniqueness is automatic: The set() constructor automatically discards any duplicate items from the input.
• Basic operations:
  • my_set.add(element) adds a single element.
  • my_set.remove(element) removes an element. It will raise a KeyError if the element doesn't exist.
  • len(my_set) returns the number of items in the set.
  • element in my_set checks for membership and returns True or False.

One important detail to remember is how to create an empty set. Using empty curly braces {} creates an empty dictionary, not an empty set. To create an empty set, you must use the constructor without any arguments: empty_set = set().

This table provides a handy summary of the basic operations.

Problem 1: Finding Unique Elements in a Collection

Now, let's focus on the primary learning outcome for this lesson. A very common requirement in programming is to take a list that might contain duplicates and produce a new list with only the unique elements. With sets, this task becomes remarkably simple and efficient.

The standard pattern is:

1. Convert the original list to a set. This automatically handles the removal of all duplicates.
2. Convert the resulting set back into a list.

This image shows this exact process in a code editor.

Let's watch a short clip that walks through this specific use case.

The code for this pattern is typically written as a single, readable line:

numbers = [1, 2, 5, 2, 4, 5, 1, 3]
unique_numbers = list(set(numbers))
print(unique_numbers) # Output might be [1, 2, 3, 4, 5] (order is not guaranteed)

From an algorithmic perspective, this is highly efficient. Creating the set from the list takes, on average, time proportional to the number of elements in the list (O(n)). This is much faster than a manual approach, which might involve iterating through the list and for each element, checking if you've seen it before—a process that could be O(n²).

Solving More Complex Problems with Sets

The power of sets extends beyond just finding unique items. Their efficient operations for intersection, difference, and membership testing make them a go-to tool for a variety of algorithmic problems.

The following reading assignment from CodeSignal is structured perfectly for an aspiring interviewee. It presents common problems and shows how to solve them elegantly and efficiently with sets.

Let's recap the powerful problem-solving patterns from the article:

1. Finding Common Elements (Intersection): To find elements present in two different lists, list1 and list2, you can convert both to sets and find their intersection.

   common_elements = set(list1) & set(list2)
   

2. Finding Unique-to-List Elements (Difference): To find elements that are in list1 but not in list2, use set difference.

   unique_to_list1 = set(list1) - set(list2)
   

3. Finding Non-Repeating Elements: To find elements that appear exactly once in a single list, the two-set algorithm is very clever:

   • Iterate through the list.
   • Use a seen set to track every element you encounter.
   • Use a duplicates set to track elements you've seen more than once.
   • The final result is the difference between seen and duplicates.

Practice Exercise

Now it's your turn to apply what you've learned.

Problem:
Imagine you're analyzing website data. You have two lists:

• visitors: A list of user IDs for everyone who visited the site today.
• purchasers: A list of user IDs for everyone who made a purchase today.

Write a Python function find_non_purchasers(visitors, purchasers) that returns a list of user IDs of people who visited the site but did not make a purchase. The returned list should not contain any duplicate user IDs.

Example:

visitors = [101, 102, 103, 104, 105, 102]
purchasers = [102, 104]



# The function should return a list containing 101, 103, and 105 (order doesn't matter).

Take a moment to think about how you would solve this using sets.

def find_non_purchasers(visitors, purchasers):



    # Convert both lists to sets to handle duplicates and allow for set operations
    visitor_set = set(visitors)
    purchaser_set = set(purchasers)
    



    # Find the difference between the two sets
    non_purchaser_set = visitor_set - purchaser_set
    



    # Convert the result back to a list before returning
    return list(non_purchaser_set)




# Example usage:
visitors = [101, 102, 103, 104, 105, 102]
purchasers = [102, 104]
non_purchasers = find_non_purchasers(visitors, purchasers)
print(non_purchasers) # Expected output (order may vary): [101, 103, 105]

Conclusion

In this lesson, you put the theory of sets into practice. You learned the essential Python syntax for working with sets and, most importantly, how to apply them to solve common problems efficiently.

Key Takeaways:

• Sets are created in Python using set() or curly braces {} (but set() is required for an empty set).
• The most direct way to get unique elements from a list is the list(set(my_list)) pattern.
• Because sets are built on hash tables, they are extremely efficient for tasks involving uniqueness, membership testing, and comparisons between collections.
• Set operations like intersection (&) and difference (-) are powerful tools for solving common algorithmic problems, such as finding common friends or filtering data.

Preview of the Next Lesson:

You have now completed the module on Hash Tables, covering both dictionaries and sets. You've built a solid foundation in using these key-based and element-based lookup structures.

In the next module, we will venture into a new and fundamental area of data structures: Trees. We will start by moving away from linear or unordered collections and learning about hierarchical data. The first lesson will define key tree terminology like root, parent, child, leaf, height, and depth, which will form the vocabulary for all future discussions on tree-based algorithms.