🧩 Sets

Why it matters

Sets remove duplicates and give O(1) average membership checks — perfect for many DSA problems.

The idea

A set is a bag of unique, hashable items with no ordering. Operations from school: | union, & intersection, - difference, ^ symmetric difference.

Try it

Deduplication and membership:

nums = [1, 1, 2, 3, 3, 5, 5, 7]
unique = set(nums)
print(unique, "size:", len(unique))

print(5 in unique)   # O(1) average
print(9 in unique)

Set algebra:

a = {"red", "green", "blue", "yellow"}
b = {"green", "blue", "purple"}
print("union        ", a | b)
print("intersection ", a & b)
print("a only       ", a - b)
print("xor          ", a ^ b)

A classic interview problem — first repeating character:

def first_repeat(s):
  seen = set()
  for ch in s:
      if ch in seen:
          return ch
      seen.add(ch)
  return None

for w in ["abcdea", "abcde", "swiss"]:
  print(w, "->", first_repeat(w))

Core methods

| Method | What it does | Example | | --- | --- | --- | | add(x) | add one | st.add(3) | | update(iter) | add many | st.update([4,5]) | | remove(x) | remove; error if missing | st.remove(2) | | discard(x) | remove safely | st.discard(2) | | pop() | remove arbitrary | st.pop() | | clear() | remove all | st.clear() | | copy() | shallow copy | st.copy() |

Subset / superset checks

A <= B   # subset
A <  B   # proper subset
A >= B   # superset

Set comprehension and frozenset

squares = {x*x for x in range(5)}   # set comprehension
fs = frozenset([1, 2, 3])           # immutable, hashable set

Quick check

• Q: Is {} a set? A: No, it's a dict. Use set() for an empty set.

Mini drills

• Count unique words in a sentence.
• Check if a list has duplicates.

Do's and don'ts

• Do use sets for membership checks.
• Don't rely on set order.

Common mistakes

• Mistake: Using {} for an empty set. Fix: Use set().
• Mistake: Expecting order in a set. Fix: Use a list if order matters.

Key takeaways

• Sets store unique, hashable items; lookup is O(1) average.
• Set algebra (|, &, -, ^) is fluent and fast.
• "Have I seen this before?" → reach for a set.
• frozenset is the immutable, hashable variant — can be a dict key.