Sets — Uniqueness & O(1) Membership
BeginnerSets store unique, unordered, hashable elements with O(1) membership tests and algebra operators (| & - ^) — the tool for dedupe, "seen" tracking, and intersection problems.
Overview
A set is a dict without values: unique elements, hash-based O(1) membership, no order. Two moves make sets essential in interviews: converting a list to a set to dedupe or to accelerate "x in collection" from O(n) to O(1), and using set algebra (union, intersection, difference) to answer "common elements / missing elements" questions in one line. frozenset is the immutable, hashable variant.
Dedupe, Membership & the "seen" Pattern
set(list) removes duplicates (order lost). The seen-set pattern is the backbone of two-sum, duplicate detection, and cycle detection.
emails = ["a@x.com", "b@x.com", "a@x.com"]
unique = set(emails) # {'a@x.com', 'b@x.com'}
print(len(emails) != len(unique)) # True -> duplicates exist
# O(1) membership vs list's O(n)
blocked = {"spam@x.com", "bot@x.com"}
if "spam@x.com" in blocked: # O(1)
print("blocked")
# Two Sum with a seen-set — O(n)
def two_sum_exists(nums, target):
seen = set()
for n in nums:
if target - n in seen:
return True
seen.add(n)
return False
print(two_sum_exists([3, 8, 1, 9], 10)) # True (1+9)
s = set() # empty set — {} is an empty DICT!
s.add(5); s.discard(99) # discard never raises; remove() doesSet Algebra
Union |, intersection &, difference -, symmetric difference ^. Subset/superset checks with <= and >=. These turn multi-loop problems into one-liners.
java_students = {"asha", "ravi", "neha", "kiran"}
python_students = {"neha", "kiran", "vikram"}
print(java_students & python_students) # both: {'neha', 'kiran'}
print(java_students | python_students) # either: all 5
print(java_students - python_students) # java only: {'asha', 'ravi'}
print(java_students ^ python_students) # exactly one: {'asha','ravi','vikram'}
print({"neha"} <= java_students) # subset? True
# Find missing numbers in one line
expected = set(range(1, 8))
present = {1, 2, 4, 6}
print(sorted(expected - present)) # [3, 5, 7]
# frozenset — immutable, so usable as a dict key
cache = {frozenset(["read", "write"]): "rw-role"}Key Points to Remember
- 1O(1) average add/remove/contains; elements must be hashable; no order
- 2{} is an empty dict — use set() for an empty set
- 3The seen-set pattern converts O(n²) scans into O(n)
- 4& | - ^ solve common/missing-element questions in one line
Interview Questions
Sign in to ask AriaFind common elements of two lists efficiently. Complexity before and after using sets?
Why must set elements be hashable? What happens with a list element?
Check if a list contains duplicates — three approaches with trade-offs.
Ask Aria about Sets — Uniqueness & O(1) Membership
Your personal AI tutor — ask anything about this concept
Revision Status
Personal Notes
Sign in to save personal notes for this topic.
Discussion
Sign in to join the discussion.