# Have I Seen This Before? Sets

Count the different members who came to the gym today, and know at each scan whether it's someone's first visit: why counting scans, a list and a dictionary of "true" each fall short, and how your language's set answers "have I seen this before?" in one step.

Apprentice · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Use a set to check in O(1) time on average whether you've seen an item before
- Remove duplicates from a list with a set, and keep the original order when it matters

## Key takeaways

- Checking a list of everyone seen so far makes a day of n scans O(n²); a dictionary works, but stores a value nobody ever reads.
- A set holds each item at most once, and answers "is this in here?" in O(1) time on average.
- A set is a hash table that keeps only keys: C#'s and Java's HashSet, Python's set and JavaScript's Set.
- Turning a list into a set removes its duplicates in one line, but a set doesn't promise to keep the list's order.
- To remove duplicates and keep the order, walk the list once, keeping each item the first time the set hasn't seen it.

**Before this:** *The Front Desk Finds You in One Scan: Dictionaries*, where every key had a value stored under it.

The gym's owner wants one number at the end of each day: how many different members came in. It decides how many staff to put on tomorrow. The front desk wants something smaller, at every scan: is this the member's first visit today? A first visit gets "Welcome", a second one "Welcome back".

The catch is Maya. She scans her card at 7 a.m., leaves for a coffee, and scans again at 7:30. She's one visitor, not two. Since the second branch opened, a busy day brings about 5,000 scans from about 4,000 different members.

"Have I seen this before?" is one of the questions code asks most: has this email already signed up, has this order already been charged, has this page already been visited, is this word in the dictionary.

## What would you try?

Here's one morning's scans, to try each idea on: Maya, Leo, Maya, Priya, Leo, Sam.

**Count the scans.** One step per scan, and wrong: six scans, but four people.

**Keep a list of today's visitors, and check it at each scan.** Before adding a name, read the list to see whether it's there. The answer is right: 4 visitors, and the desk knows at each scan. But each check reads the list so far, and by evening that list holds thousands of names. For 5,000 scans that's around 10 million name checks, the handshakes of *Why the Duplicates Button Crawls: O(n²)*: twice the scans, about four times the work.

**Sort the day's scans, then count where the name changes.** Sorted, the morning reads Leo, Leo, Maya, Maya, Priya, Sam, and the name changes 3 times after the first, so there are 4 visitors. That's O(n log n), fast enough for the day's number. But the desk asks its question at every scan, and the day can't be sorted again each time a card goes through.

**Use a dictionary from each name to `true`.** Each check is one step, O(1) on average, so the day is O(n), and the desk gets its answer at every scan. It works. But look at what it stores: `true`, under every name, about 4,000 times, and nothing ever reads it. The only question asked is whether the key is there.

| What we tried | Each scan | The whole day | Where it falls short |
|---|---|---|---|
| Count the scans | O(1) | O(n) | counts Maya twice |
| A list of visitors | O(n) | O(n²): about 10 million checks | slows down as the day fills up |
| Sort, then count changes | n/a | O(n log n) | no answer until the day is over |
| A dictionary of `true` | O(1) on average | O(n) | stores a value nobody reads |

## The questions that lead to it

**What does the desk do most?** Two things, 5,000 times a day: ask "is this name in here?", and add a name. Both have to be fast, and the dictionary makes them fast.

**What does it never need?** The value. Nobody asks what's stored under Maya; only whether Maya is there.

So what if we kept the dictionary's speed and dropped the value? A hash table of keys alone.

## How it got its name

This idea is so useful that it has its own name: a **set**. The word comes from math, where a set is a group of things in which each one counts once. Every language has one built in, and it's what the dictionary-of-`true` try was reaching for: a hash table that keeps only keys. So checking whether an item is there hashes it and looks in one bucket, **O(1) on average**, however many items the set holds.

A guest list at a party door is a set you already know. The bouncer doesn't care what you brought or where you'll sit, only whether your name is on the list, and each name is on it once.

![A bouncer at a party door checking an arriving guest, Leo, against a short guest list of four names, Maya, Leo, Priya and Sam, each written once: the list holds names only, and the one question is whether the name is on it](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/dba2fa16d4cd4068b2294f49980006b7.webp)

| Language | The set | Add | Is it there? |
|---|---|---|---|
| C# | `HashSet<string>` | `Add(item)` | `Contains(item)` |
| Java | `HashSet<String>` | `add(item)` | `contains(item)` |
| Python | `set` | `add(item)` | `item in s` |
| JavaScript and TypeScript | `Set` | `add(item)` | `has(item)` |

## Checking members in

This code goes through the morning's card scans. A set remembers who has already come in, so each member is welcomed once:

```csharp
string[] scans = { "Maya", "Leo", "Maya", "Priya", "Leo", "Sam" };
HashSet<string> checkedIn = new HashSet<string>();

foreach (string name in scans)
{
    if (checkedIn.Contains(name))
    {
        Console.WriteLine(name + " is already checked in");
    }
    else
    {
        checkedIn.Add(name);
        Console.WriteLine("Welcome, " + name);
    }
}
Console.WriteLine("Visitors today: " + checkedIn.Count);
```

```text
Welcome, Maya
Welcome, Leo
Maya is already checked in
Welcome, Priya
Leo is already checked in
Welcome, Sam
Visitors today: 4
```

```java
void main() {
    String[] scans = { "Maya", "Leo", "Maya", "Priya", "Leo", "Sam" };
    Set<String> checkedIn = new HashSet<>();

    for (String name : scans) {
        if (checkedIn.contains(name)) {
            IO.println(name + " is already checked in");
        } else {
            checkedIn.add(name);
            IO.println("Welcome, " + name);
        }
    }
    IO.println("Visitors today: " + checkedIn.size());
}
```

```text
Welcome, Maya
Welcome, Leo
Maya is already checked in
Welcome, Priya
Leo is already checked in
Welcome, Sam
Visitors today: 4
```

```python
scans = ["Maya", "Leo", "Maya", "Priya", "Leo", "Sam"]
checked_in = set()

for name in scans:
    if name in checked_in:
        print(f"{name} is already checked in")
    else:
        checked_in.add(name)
        print(f"Welcome, {name}")
print(f"Visitors today: {len(checked_in)}")
```

```text
Welcome, Maya
Welcome, Leo
Maya is already checked in
Welcome, Priya
Leo is already checked in
Welcome, Sam
Visitors today: 4
```

```javascript
const scans = ["Maya", "Leo", "Maya", "Priya", "Leo", "Sam"];
const checkedIn = new Set();

for (const name of scans) {
  if (checkedIn.has(name)) {
    console.log(`${name} is already checked in`);
  } else {
    checkedIn.add(name);
    console.log(`Welcome, ${name}`);
  }
}
console.log(`Visitors today: ${checkedIn.size}`);
```

```text
Welcome, Maya
Welcome, Leo
Maya is already checked in
Welcome, Priya
Leo is already checked in
Welcome, Sam
Visitors today: 4
```

```typescript
const scans: string[] = ["Maya", "Leo", "Maya", "Priya", "Leo", "Sam"];
const checkedIn = new Set<string>();

for (const name of scans) {
  if (checkedIn.has(name)) {
    console.log(`${name} is already checked in`);
  } else {
    checkedIn.add(name);
    console.log(`Welcome, ${name}`);
  }
}
console.log(`Visitors today: ${checkedIn.size}`);
```

```text
Welcome, Maya
Welcome, Leo
Maya is already checked in
Welcome, Priya
Leo is already checked in
Welcome, Sam
Visitors today: 4
```

Each scan is one O(1) check, so a whole day of n scans is O(n), where the list of visitors made it O(n²). The 5,000-scan day is 5,000 checks, not 10 million.

Adding an item that's already in a set does nothing: no error, no second copy. In C# and Java, `Add` also tells you which happened (it returns `true` only when the item was new), so `if (checkedIn.Add(name))` does the check and the add in one step.

## Removing duplicates

Here's the walk you just saw, written to keep a list: the members in the order they first came in, each once. Because the set remembers what's already been kept, the walk is one pass, O(n), and the order of arrival is kept:

```csharp
string[] scans = { "Maya", "Leo", "Maya", "Priya", "Leo", "Sam" };

Console.WriteLine("Different members: " + new HashSet<string>(scans).Count);

HashSet<string> seen = new HashSet<string>();
List<string> inOrder = new List<string>();
foreach (string name in scans)
{
    if (seen.Add(name))
    {
        inOrder.Add(name);
    }
}
Console.WriteLine("In order of arrival: " + string.Join(", ", inOrder));
```

```text
Different members: 4
In order of arrival: Maya, Leo, Priya, Sam
```

```java
void main() {
    List<String> scans = List.of("Maya", "Leo", "Maya", "Priya", "Leo", "Sam");

    IO.println("Different members: " + new HashSet<>(scans).size());

    Set<String> seen = new HashSet<>();
    List<String> inOrder = new ArrayList<>();
    for (String name : scans) {
        if (seen.add(name)) {
            inOrder.add(name);
        }
    }
    IO.println("In order of arrival: " + String.join(", ", inOrder));
}
```

```text
Different members: 4
In order of arrival: Maya, Leo, Priya, Sam
```

```python
scans = ["Maya", "Leo", "Maya", "Priya", "Leo", "Sam"]

print(f"Different members: {len(set(scans))}")

seen = set()
in_order = []
for name in scans:
    if name not in seen:
        seen.add(name)
        in_order.append(name)
print(f"In order of arrival: {', '.join(in_order)}")
```

```text
Different members: 4
In order of arrival: Maya, Leo, Priya, Sam
```

```javascript
const scans = ["Maya", "Leo", "Maya", "Priya", "Leo", "Sam"];

console.log(`Different members: ${new Set(scans).size}`);

const seen = new Set();
const inOrder = [];
for (const name of scans) {
  if (!seen.has(name)) {
    seen.add(name);
    inOrder.push(name);
  }
}
console.log(`In order of arrival: ${inOrder.join(", ")}`);
```

```text
Different members: 4
In order of arrival: Maya, Leo, Priya, Sam
```

```typescript
const scans: string[] = ["Maya", "Leo", "Maya", "Priya", "Leo", "Sam"];

console.log(`Different members: ${new Set(scans).size}`);

const seen = new Set<string>();
const inOrder: string[] = [];
for (const name of scans) {
  if (!seen.has(name)) {
    seen.add(name);
    inOrder.push(name);
  }
}
console.log(`In order of arrival: ${inOrder.join(", ")}`);
```

```text
Different members: 4
In order of arrival: Maya, Leo, Priya, Sam
```

The first line is the one-line way: make a set from the list, and the duplicates are gone. It's the right tool when you only need the count, or don't care about order.

**Where the languages differ: order.** A set, like a dictionary, doesn't promise an order in every language. JavaScript's `Set` keeps the order items were added. Python's `set` and Java's `HashSet` don't, and C#'s `HashSet` doesn't promise to. Some languages have a shortcut that keeps the order: Python's `list(dict.fromkeys(scans))`, Java's `new LinkedHashSet<>(scans)` and JavaScript's `[...new Set(scans)]`. The walk with a `seen` set works in all five.

**Two groups at once:** sets also answer "who's in both?". Members who came on Monday and on Tuesday are the **intersection** of the two days' sets: `IntersectWith` in C#, `retainAll` in Java, `&` in Python, and in JavaScript a filter, `[...monday].filter((name) => tuesday.has(name))`.

## The cost card

| Operation | Big-O | The everyday reason |
|---|---|---|
| Add an item | O(1) on average | Hash it, drop it in its bucket |
| Is it in the set? | O(1) on average | Hash it, look in one bucket |
| Remove an item | O(1) on average | Hash it, take it out of its bucket |
| Remove the duplicates from a list of n items | O(n) | One pass, one O(1) check per item |
| The same question on a list instead of a set | O(n) per check | Read the list from the top |

**When something else wins.** If you only need the day's number, once, from a file of scans, sorting and counting the changes is fine too, though a set is less code. For a few dozen names, a list is fine. And when the answer has to come out in A to Z order, make the set first, then sort the k different names, O(k log k), not all n scans.

## Check yourself

2 questions to try on the lesson page.

## So what

Whenever code asks "have I seen this before?", a set turns the question from a search into one step. It's the quiet fix behind many "why is this loop so slow?" code reviews.

## Key terms

- [Set](https://www.ask-codey.com/glossary/set-data-structures)
- [HashSet&lt;T>](https://www.ask-codey.com/glossary/hashset-t)
- [HashSet](https://www.ask-codey.com/glossary/hashset)
- [Set](https://www.ask-codey.com/glossary/set)
- [Set](https://www.ask-codey.com/glossary/set-javascript)

## Cheat sheets

- [Have I Seen This Before? Sets](https://www.ask-codey.com/cheat-sheets/ds-sets-cheat-sheet)

Source: https://www.ask-codey.com/lessons/ds-sets
