Sets

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 1 Time to complete: ~20 minutes

Table of Contents

1. What a Set Is
2. O(1) Average Membership Testing
3. Set Operations
4. Set vs. Dict — When to Use Which
5. Summary & Next Steps

1. What a Set Is

A set is a hash map that only stores keys, no values — it's built on exactly the same hashing machinery as dict (Chapter 1), so it inherits the same performance characteristics. You already met sets briefly in Python Notes Module 1 Chapter 9; this chapter revisits them through a complexity lens.

fruits = {"apple", "banana", "cherry"}
fruits.add("date")
fruits.remove("banana")
print("apple" in fruits)      # True

Sets are unordered and contain no duplicates — adding an existing element is a no-op.

2. O(1) Average Membership Testing

This is the payoff of the entire chapter, and it's the exact fix for Module 1 Chapter 1's motivating example:

numbers_list = list(range(1_000_000))
numbers_set = set(range(1_000_000))
 
500_000 in numbers_list     # O(n) — scans up to a million items
500_000 in numbers_set      # O(1) average — hashes directly to the bucket

Whenever you find yourself repeatedly checking x in some_list inside a loop (the "hidden nested loop" trap from Module 1 Chapter 6), converting some_list to a set up front is almost always the fix — it turns an O(n × m) algorithm into O(n + m).

3. Set Operations

Sets support the mathematical set operations directly, each running in time proportional to the size of the smaller set on average:

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}
 
print(a | b)     # union: {1, 2, 3, 4, 5, 6} — everything in either set
print(a & b)     # intersection: {3, 4} — only what's in both
print(a - b)     # difference: {1, 2} — in a but not in b
print(a ^ b)     # symmetric difference: {1, 2, 5, 6} — in exactly one of the two
 
print(a.issubset({1, 2, 3, 4, 5}))     # True — every element of a is in the other set
print(a.isdisjoint({7, 8}))              # True — no elements in common

These operators are frequently the fastest way to compare two collections — e.g., "which elements appear in both lists" is set(list_a) & set(list_b), O(n + m), versus a nested-loop comparison at O(n × m).

4. Set vs. Dict — When to Use Which

A useful rule of thumb: if you catch yourself writing {key: True for key in items} just to get fast membership testing, use a set instead — it's the same underlying structure with less overhead.

5. Summary & Next Steps

Key Takeaways

• A set is a hash map with keys only — same O(1) average membership testing as dict.
• Converting a list to a set before repeated membership checks is one of the single most common optimizations in interview problems.
• Set operators (|, &, -, ^) express union/intersection/difference/symmetric-difference directly and efficiently.
• Use a set when you only need "does this exist"; use a dict when you need to attach a value (like a count) to each key.

Concept Check

1. Why does converting a list to a set before a membership check in a loop change the overall complexity?
2. What does a & b compute, and what's its rough time complexity relative to the size of a and b?
3. When would you reach for a dict instead of a set?

Next Chapter

→ Chapter 3: Frequency Counting Pattern

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index