AI Hints
Home›DSA in Python Tutorial›Sets and Hashing Practice
DSA in Python · Lesson 22 of 132

Sets

Fast membership and unique items.

⏱ 2 min read▶ Video at 25:19🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

A set is a hash table with keys, but no values. It answers one question incredibly fast. Is this item in here? And it never holds duplicates.

Sets
From the video: Sets
  • A hash table without values
  • Is it in here? Instantly
  • No duplicates

Set operations

Sets support the maths you may remember from school. The bar means union, everything in either set. The ampersand means intersection, only what's in both. And minus means difference, what's in the first but not the second. Run it. Priya and Jo are in both clubs.

sets.pypython
chess = {"Priya", "Sam", "Jo"}
music = {"Jo", "Alex", "Priya", "Mia"}

print("either:", sorted(chess | music))
print("both:  ", sorted(chess & music))
print("chess only:", sorted(chess - music))
Output
either: ['Alex', 'Jo', 'Mia', 'Priya', 'Sam']
both:   ['Jo', 'Priya']
chess only: ['Sam']

Set costs

Adding, removing, and checking membership are all O of one on average. Union and intersection depend on the sizes of the sets. Remember, sets have no order, and they can only hold things that never change, like numbers, strings, and tuples. Not lists.

OperationExampleCost
add / removes.add(x)O(1)
membershipx in sO(1)
uniona | bO(len(a) + len(b))
intersectiona & bO(smaller set)

Summary

Sets give O of one membership checks, and remove duplicates for free. Union, intersection, and difference compare groups. Next, the most famous interview question of all. Two sum.

Key takeaways
  • x in set is O(1)
  • | & -
  • No duplicates, no order
Next up: Practice: Two Sum — the classic interview question