Sets and Their Uses

A set in Python is an unordered collection of unique, hashable elements, and it exists to answer one question extremely fast: “have I seen this value before?” Where a list has to be scanned item by item to answer that question, a set uses the exact same hash-table machinery as a dictionary to answer it in constant time on average. That single property — near-instant membership testing — makes sets one of the most useful tools in a programmer’s toolbox for deduplication, fast lookups, and comparing collections of data.

Overview / How it works

Every element you put into a set must be hashable — Python computes hash(value) for it and uses that number to decide which “bucket” of an internal array the value belongs to. This is exactly how a dict works internally; in fact, you can think of a set as a dict that only stores keys and throws away the values. That shared machinery is why sets and dicts have the same performance characteristics for adding, removing, and checking membership.

Creating and using sets

You create a set with curly braces or the set() constructor: {1, 2, 3} or set([1, 2, 3]). There is one trap here — {} creates an empty dict, not an empty set, because curly braces were dict syntax first. An empty set must be written as set(). Once you have a set, the core operations are add(value), remove(value) (raises KeyError if missing), discard(value) (silently does nothing if missing), and the membership test value in my_set.

Because duplicates are impossible in a set — adding a value that’s already present is a silent no-op — converting a list to a set is the standard, idiomatic way to deduplicate: set(my_list) keeps exactly one copy of every distinct value.

Set algebra: union, intersection, difference

Sets support the mathematical operations you’d expect, both as operators and as equivalent methods:

Operation Operator Method Meaning
Union a | b a.union(b) everything in a or b
Intersection a & b a.intersection(b) only what’s in both
Difference a - b a.difference(b) in a but not b
Symmetric difference a ^ b a.symmetric_difference(b) in exactly one of the two

Each of these also has an in-place update version — a |= b, a &= b, a -= b, a ^= b — which mutates a instead of building a new set.

frozenset: the immutable sibling

frozenset is a set that cannot be changed after creation. Because it’s immutable, it’s also hashable, which means — unlike a regular set — a frozenset can itself be stored inside another set or used as a dictionary key. Reach for it when you need a fixed collection of unique values as a lookup key, such as caching results keyed by a combination of options.

Sets vs. lists vs. dicts

Use a list when order matters and duplicates are meaningful. Use a set when you only care which distinct values are present and need fast membership tests, unions, or intersections. Use a dict when you need to associate a value with each unique key. A set is, structurally, a dict with the values stripped away — a useful way to remember why its performance profile matches a dict’s.

Time and Space Complexity

A set is backed by a hash table: a fixed-size array where each element’s bucket is chosen from hash(value) (conceptually via hash(value) % table_size, though the real implementation uses bit masking and a probing sequence — the mental model is the same). Because the bucket is computed directly from the hash instead of found by scanning, membership testing doesn’t need to look at every element the way a list does.

Operation Average case Worst case Why
x in s O(1) O(n) Hash lookup jumps straight to a bucket; worst case is many values colliding into the same bucket.
s.add(x) O(1) O(n) Same bucket lookup, plus an occasional O(n) resize when the table grows.
s.remove(x) / discard(x) O(1) O(n) Same reasoning as lookup.
a | b (union) O(len(a) + len(b)) O(len(a) + len(b)) Every element of both sets must be visited once.
a & b (intersection) O(min(len(a), len(b))) O(len(a) · len(b)) Python iterates the smaller set and checks membership in the larger one; worst case is pathological hash collisions.
a - b (difference) O(len(a)) O(len(a) · len(b)) Iterates a, checking membership in b for each element.
Building a set from n items O(n) O(n²) n insertions, each O(1) average.

Space: A set of n elements uses O(n) space, but the underlying array is usually larger than n — CPython keeps the table only up to about two-thirds full and resizes (grows) when it gets too full, so there is constant-factor overhead beyond just “n elements,” though total growth is still linear in n.

Examples

Example 1: Deduplicating with a set

The most common use of a set is removing duplicates from a collection. Converting a list to a set keeps one copy of every distinct value; if you need the result back as a sorted list for consistent display, wrap it in sorted() afterward (sets themselves have no reliable order).

def unique_visitors(logs: list[str]) -> set[str]:
    return set(logs)


logs = ["alice", "bob", "alice", "carol", "bob", "alice"]
visitors = unique_visitors(logs)
print(sorted(visitors))
print(len(visitors))

Output:

['alice', 'bob', 'carol']
3

Each string in logs is hashed and placed into a bucket; when "alice" is seen a second and third time, its hash lands in the same bucket as the first "alice" already there, an equality check confirms it’s the same value, and set() simply doesn’t add another copy. The result holds three distinct names, and sorted() gives a deterministic order to display them in even though the set itself has none.

Example 2: Set algebra for comparing groups

Set operators are a compact way to compare two groups of people, tags, or IDs, without writing any loops.

python_devs = {"Ana", "Bo", "Cid", "Dee"}
js_devs = {"Bo", "Cid", "Eve", "Fay"}

both_languages = python_devs & js_devs
only_python = python_devs - js_devs
either_language = python_devs | js_devs
exactly_one_language = python_devs ^ js_devs

print(sorted(both_languages))
print(sorted(only_python))
print(sorted(either_language))
print(sorted(exactly_one_language))

Output:

['Bo', 'Cid']
['Ana', 'Dee']
['Ana', 'Bo', 'Cid', 'Dee', 'Eve', 'Fay']
['Ana', 'Dee', 'Eve', 'Fay']

both_languages keeps only names present in both sets (Bo and Cid). only_python keeps names in python_devs that aren’t in js_devs (Ana and Dee). either_language merges everyone from both sets with no duplicates. exactly_one_language keeps everyone except the overlap — the symmetric difference. None of this required a single explicit loop.

Example 3: Using a set for O(1) lookups in an algorithm

This is a pattern that shows up constantly in interviews: instead of nesting a loop inside a loop to compare every pair of numbers (O(n²)), keep a set of numbers seen so far and check it as you go (O(n)).

def has_pair_with_sum(nums: list[int], target: int) -> bool:
    seen: set[int] = set()
    for num in nums:
        complement = target - num
        if complement in seen:
            return True
        seen.add(num)
    return False


nums = [10, 15, 3, 7]
target = 17
print(has_pair_with_sum(nums, target))

Output:

True

Trace it by hand: seen starts empty. For 10, the needed complement is 7, which isn’t in seen yet, so 10 is added. For 15, the complement 2 isn’t present, so 15 is added. For 3, the complement 14 isn’t present, so 3 is added. For 7, the complement is 10 — and 10 is already in seen — so the function returns True immediately, having found that 10 + 7 == 17. Each membership check and insertion is O(1) average, so the whole scan is O(n) instead of the O(n²) you’d get comparing every pair with nested loops.

How it works step by step

To make “O(1) average” concrete, walk through inserting three integers — 12, 20, and 5 — into a set, using a simplified model of the underlying hash table with 8 buckets (Python resizes automatically, but the mechanics are the same idea at any size):

  1. Insert 12: compute hash(12) % 8 = 4. Bucket 4 is empty, so 12 is placed there.
  2. Insert 20: compute hash(20) % 8 = 4. Bucket 4 is occupied by 12, so this is a collision — the table probes to the next available bucket (bucket 5) and places 20 there.
  3. Insert 5: compute hash(5) % 8 = 5. Bucket 5 is occupied by 20, another collision, so it probes to bucket 6 and places 5 there.
  4. Look up 20: compute hash(20) % 8 = 4, check bucket 4 — it holds 12, not 20, so the equality check fails and the probe continues to bucket 5, which holds 20 — a match is found in two quick steps rather than scanning every element.

This is also why a set’s iteration order looks arbitrary and can change as you add or remove elements: it reflects bucket positions, not insertion order. When most buckets are empty — which Python maintains by resizing before the table gets too full — collisions like this are rare, which is exactly why lookups average out to O(1) instead of degrading toward O(n).

Common Mistakes

Mistake 1: Treating a set like it’s ordered or indexable

Sets have no positional order, so indexing one raises an error, and even when it doesn’t error, relying on “the order I put things in” is a bug waiting to happen:

unique_ids = {101, 102, 103}
first_id = unique_ids[0]
print(first_id)

Output:

TypeError: 'set' object is not subscriptable

Sets don’t support [] indexing at all, because there’s no “position 0” in a hash table — only buckets. If you need the “next” element without caring which one, use next(iter(my_set)); if you need a specific order, convert to a sorted list first:

unique_ids = {101, 102, 103}
first_id = next(iter(unique_ids))
print(first_id)

Output:

101

This prints 101 only because of how these particular small integers happen to land in the hash table — never write code whose correctness depends on that. If you need a specific element, filter for it explicitly; if you need “some” element and genuinely don’t care which, next(iter(...)) is fine precisely because you’re declaring you don’t care.

Mistake 2: Adding an unhashable value

Only hashable, effectively-immutable types can go inside a set — this rules out lists, dicts, and other sets, since Python requires a stable hash for the lifetime of the object:

seen_pairs = set()
seen_pairs.add([1, 2])

Output:

TypeError: unhashable type: 'list'

The fix is to use an immutable equivalent — a tuple instead of a list:

seen_pairs = set()
seen_pairs.add((1, 2))
print(seen_pairs)

Output:

{(1, 2)}

This comes up constantly when tracking visited coordinates in a grid, or visited (row, col) pairs during a graph search — always store them as tuples, not lists, if they’re going into a set.

Mistake 3: Checking membership against a list instead of a set inside a loop

Using in on a list is O(n) — perfectly fine once, but disastrous inside a loop, where it silently turns an O(n) algorithm into O(n · m):

def count_common_slow(a: list[int], b: list[int]) -> int:
    count = 0
    for x in a:
        if x in b:  # scans all of b, every single time
            count += 1
    return count

For every element of a, this rescans the entire list b from the start. With a and b both size n, that’s O(n²) total work. Converting b to a set once, before the loop, fixes it, because membership testing against a set is O(1) average instead of O(n):

def count_common_fast(a: list[int], b: list[int]) -> int:
    b_set = set(b)
    count = 0
    for x in a:
        if x in b_set:  # O(1) average lookup
            count += 1
    return count


a = [1, 2, 3, 4]
b = [3, 4, 5, 6]
print(count_common_fast(a, b))

Output:

2

Tracing it: b_set is {3, 4, 5, 6}. Walking through a: 1 isn’t in b_set, 2 isn’t either, 3 is (count becomes 1), and 4 is (count becomes 2). The final count is 2, and the whole function ran in O(len(a) + len(b)) instead of O(len(a) · len(b)).

Best Practices

  • Reach for a set the moment you catch yourself writing if x in some_list: inside a loop — that’s almost always an O(n²) algorithm waiting to become O(n).
  • Use a set to deduplicate (set(my_list)) whenever you only care about distinct values, then convert back with sorted() or list() if you need a concrete order afterward.
  • Never rely on the iteration order of a set. If order matters, use a list, a sorted structure, or a dict (which does guarantee insertion order).
  • Only put hashable, effectively-immutable values into a set — use tuple instead of list, and frozenset instead of set, when you need a “set of collections.”
  • Prefer the operators (|, &, -, ^) for readability when both sides are already sets, and the methods (.union(), .intersection(), etc.) when combining a set with any iterable — the methods accept any iterable while the operators require both operands to be sets.
  • Avoid rebuilding a set inside a loop that runs many times; build it once, outside the loop, and reuse it.

Practice Exercises

  1. Find duplicates: Write a function find_duplicates(nums: list[int]) -> set[int] that returns the set of values that appear more than once in nums. For [4, 3, 2, 7, 8, 2, 3, 1], the expected result is {2, 3}. (Hint: track values you’ve already seen in one set, and confirmed duplicates in a second set.)
  2. Common elements across many lists: Given a list of lists, e.g. [[1, 2, 3], [2, 3, 4], [2, 5, 3]], write a function that returns the set of values present in every sublist, using repeated intersection. Expected result: {2, 3}.
  3. Anagram check with sets vs. Counter: Write is_anagram(a: str, b: str) -> bool. First try set(a) == set(b) and explain, with a specific example, why that’s wrong for strings with repeated letters (hint: try "aab" and "abb"). Then fix it using collections.Counter instead.

Summary

  • A set is an unordered collection of unique, hashable values, backed by the same hash-table mechanism as a dict.
  • Membership testing, adding, and removing are O(1) on average and O(n) in the rare worst case of many hash collisions.
  • Set algebra — | (union), & (intersection), - (difference), ^ (symmetric difference) — runs in time proportional to the sizes of the sets involved, not their product.
  • Sets guarantee uniqueness but never order; use a dict or list when order matters.
  • Only hashable values (numbers, strings, tuples, frozensets) can live inside a set — not lists, dicts, or other sets.
  • The single biggest practical win: replacing if x in some_list inside a loop with a set turns an O(n²) algorithm into an O(n) one.