What is a set and what problems does it solve?

Question

Accepted Answer

A **set** is an unordered collection of **unique** elements. Its core power is answering "is X in here?" in **average O(1)**, and it automatically rejects duplicates.

## Example

```python
seen = set()
seen.add('a')
seen.add('a')          # ignored — already present
print(len(seen))       # 1
'a' in seen            # O(1) average membership test

# Set algebra
a = {1, 2, 3}
b = {2, 3, 4}
a & b                  # intersection -> {2, 3}
a | b                  # union        -> {1, 2, 3, 4}
a - b                  # difference   -> {1}
```

Most sets are implemented as **hash sets** (a hash table storing only keys), so:

| Operation | Average |
|---|---|
| add | O(1) |
| remove | O(1) |
| membership (`in`) | O(1) |

## Common uses

- **Deduplication** — remove repeats from a list in one line.
- **Fast membership** — "have I seen this before?"
- **Relationships** — intersection/union/difference between groups.

## Why it matters

Sets make "uniqueness" and "membership" trivial and fast, replacing slow nested loops over lists.

A common interview trick — detecting duplicates or visited nodes — collapses to a few set operations.