Data structure 4 of 12

Hash sets

A hash set is a hash map with keys and no values. It answers one question very fast: is this item here? It also throws away duplicates for free.

A 2-minute conversation: Sam asks, Priya explains

0:00 / 2:16

Follow along on the page Pause on “your turn” questions

Sam Hash sets. A map without the values?
Priya Exactly. It answers one question very fast: is this item here? And it throws away duplicates for free.
Priya Think of the stamp on your hand at a festival. The gate staff only check one thing: stamp or no stamp. They don't care what you paid. And a second stamp doesn't make you twice as admitted.
Sam So when do I use a set instead of a map?
Priya When you only need "in or out". If you need counts, positions or order, use something else.
Sam How does it work inside?
Priya Like a map's keys. Items go into buckets by their hash, and a membership check looks in one bucket. And because sets are about membership, they combine: union is everything in either, intersection is what's in both, difference is what's in one but not the other.
Sam Costs?
Priya Add, remove and membership are constant on average. Building a set from a list is linear. Intersection costs the size of the smaller set.
Priya Your turn. A loop checks whether each word is in a list of ten thousand banned words. What's the fix?
Priya Convert the list to a set once, before the loop. Each check drops from linear to constant.
Sam Any surprises across languages?
Priya In Python, empty curly braces make a dictionary, not a set: write set with brackets. And in TypeScript, arrays compare by identity, so store grid positions as strings like "zero comma one".
Sam The players?
Priya Remove duplicates while keeping the order: the set remembers, the list keeps order. Find what two lists have in common. And remember positions you've visited, which is the visited set behind every grid and graph search.
Sam Memory hook?
Priya The hand stamp. In or out, no counting, no order.
Sam Problems?
Priya Path crossing, where you walk north, south, east and west and ask whether you've stood somewhere before. Intersection of two arrays. And the difference of two arrays, in both directions.
Sam Mistakes?
Priya Searching a list in a loop. Expecting order. Putting lists in a set, which Python refuses. And using a set when you need counts.
Sam Next?
Priya Lesson five, linked lists, where order is kept by arrows instead of positions.

1. What it is

The stamp on your hand at a music festival. Staff at the gate don't look up your name in a book or ask what you paid; they only check one thing: stamp or no stamp. And a second stamp doesn't make you twice as admitted.

A set (Python set, TypeScript Set, Java HashSet) holds unique items in no particular order. It is built exactly like a hash map's keys, so the same costs apply.

Fast: add, remove and "is x in the set?", all O(1) on average.
Free: duplicates disappear; adding an item twice keeps one.
Not for: anything that needs counts (use a map), positions (use a list or a map) or sorted order.

2. How it sits in memory

Items go into buckets chosen by their hash, just like map keys, but nothing is stored alongside them. A membership test hashes the item and looks in one bucket.

Because sets are about membership, they combine naturally: everything in either (union), only what's in both (intersection), or what's in one but not the other (difference).

3. Operations and what they cost

Operation	Python	Cost
Add, remove	`s.add(x)`, `s.discard(x)`	`O(1)` average
Membership	`x in s`	`O(1)` average (a list is `O(n)`)
Build from a list	`set(nums)`	`O(n)`
Union	`a \| b`	`O(len a + len b)`
Intersection	`a & b`	`O(min(len a, len b))`
Difference	`a - b`	`O(len a)`

The cheapest speed-up in interviewsif x in my_list inside a loop is O(n) each time. Convert the list to a set once before the loop and it becomes O(1).

4. In Python, TypeScript and Java

The everyday set moves in each language.

seen = set()
    seen.add(3)
    seen.add(3)                # still {3}
    print(3 in seen)           # True
    seen.discard(7)            # no error if missing
    a, b = {1, 2, 3}, {2, 3, 4}
    print(a | b, a & b, a - b) # {1, 2, 3, 4} {2, 3} {1}
    unique = set([4, 1, 4, 2]) # {1, 2, 4}, order not guaranteed
    visited = {(0, 0), (0, 1)} # tuples work as items

const seen = new Set<number>();
    seen.add(3);
    seen.add(3);                              // still {3}
    console.log(seen.has(3));                 // true
    seen.delete(7);
    const a = new Set([1, 2, 3]), b = new Set([2, 3, 4]);
    const both = [...a].filter((x) => b.has(x));   // [2, 3]
    // arrays aren't compared by value, so store positions as strings: "0,1"
    const visited = new Set<string>(["0,0", "0,1"]);

Set<Integer> seen = new HashSet<>();
    seen.add(3);
    seen.add(3);                              // still [3]
    System.out.println(seen.contains(3));     // true
    seen.remove(7);
    Set<Integer> a = new HashSet<>(List.of(1, 2, 3)), b = new HashSet<>(List.of(2, 3, 4));
    Set<Integer> both = new HashSet<>(a);
    both.retainAll(b);                        // [2, 3]
    Set<String> visited = new HashSet<>(List.of("0,0", "0,1"));

5. Core operations, step by step

Three jobs a set does better than anything else.

A · Remove duplicates, keeping the order

What it doesKeeps the first copy of each item; a set remembers what's already been kept.

Picture itStamping hands at the gate: the first time you arrive you get a stamp and go in; come back and you're waved away.

CostO(n) time and space.

The code. The set answers "seen it?"; the list keeps the order.

def dedupe(items):
    seen = set()
    out = []
    for x in items:
        if x not in seen:
            seen.add(x)
            out.append(x)
    return out

function dedupe(items: number[]): number[] {
  const seen = new Set<number>();
  const out: number[] = [];
  for (const x of items) {
    if (!seen.has(x)) {
      seen.add(x);
      out.push(x);
    }
  }
  return out;
}

static List<Integer> dedupe(int[] items) {
    Set<Integer> seen = new HashSet<>();
    List<Integer> out = new ArrayList<>();
    for (int x : items) {
        if (!seen.contains(x)) {
            seen.add(x);
            out.add(x);
        }
    }
    return out;
}

Line by line.

Line	What it does	Why
`if x not in seen`	First time we meet x?	O(1) on a set; O(n) if you checked the output list instead.
`seen.add(x); out.append(x)`	Stamp it and keep it.	The set remembers, the list keeps the order.

Watch it run. [4, 1, 4, 2, 1, 5].

Watch out for:

list(set(items)). Removes duplicates but scrambles the order. Use the loop when order matters.

B · What two lists have in common

What it doesPuts one list in a set, then keeps the items of the other that are in it.

Picture itTwo guest lists for a party: put the first on stamped hands, then walk the second queue checking stamps.

CostO(n + m), instead of O(n × m) with two loops.

The code. Build the set from one list once; each check after that is O(1).

def common(a, b):
    in_a = set(a)
    both = set()
    for x in b:
        if x in in_a:
            both.add(x)
    return sorted(both)

function common(a: number[], b: number[]): number[] {
  const inA = new Set(a);
  const both = new Set<number>();
  for (const x of b) {
    if (inA.has(x)) {
      both.add(x);
    }
  }
  return [...both].sort((p, q) => p - q);
}

static List<Integer> common(int[] a, int[] b) {
    Set<Integer> inA = new HashSet<>();
    for (int x : a) inA.add(x);
    Set<Integer> both = new TreeSet<>();
    for (int x : b) {
        if (inA.contains(x)) {
            both.add(x);
        }
    }
    return new ArrayList<>(both);
}

Line by line.

Line	What it does	Why
`in_a = set(a)`	Every item of a, ready for O(1) checks.	One O(n) pass, paid once.
`if x in in_a`	Is this item of b also in a?
`both.add(x)`	Collect it; repeats vanish.	A set, so 9 and 4 appear once even though b repeats them.

Watch it run. a = [4, 9, 5], b = [9, 4, 9, 8, 4].

Watch out for:

Nested loops. Checking every pair is O(n × m). The set makes it linear.

C · Remember positions you've visited

What it doesStores (row, column) pairs so you can ask "have I been here?" in O(1).

Picture itDropping a pebble on every square you stand on, so you know when you're walking in circles.

CostO(1) per check; O(number of positions) space.

The code. A tuple (or a "r,c" string in TypeScript and Java) is the item. This is the visited set behind every grid and graph search.

def first_repeat(moves):
    r = c = 0
    visited = {(r, c)}
    step = {"U": (-1, 0), "D": (1, 0), "L": (0, -1), "R": (0, 1)}
    for m in moves:
        dr, dc = step[m]
        r, c = r + dr, c + dc
        if (r, c) in visited:
            return (r, c)
        visited.add((r, c))
    return None

function firstRepeat(moves: string): [number, number] | null {
  let r = 0, c = 0;
  const visited = new Set<string>(["0,0"]);
  const step: Record<string, [number, number]> = { U: [-1, 0], D: [1, 0], L: [0, -1], R: [0, 1] };
  for (const m of moves) {
    const [dr, dc] = step[m];
    r += dr; c += dc;
    if (visited.has(`${r},${c}`)) {
      return [r, c];
    }
    visited.add(`${r},${c}`);
  }
  return null;
}

static int[] firstRepeat(String moves) {
    int r = 0, c = 0;
    Set<String> visited = new HashSet<>(List.of("0,0"));
    for (char m : moves.toCharArray()) {
        int dr = m == 'U' ? -1 : m == 'D' ? 1 : 0, dc = m == 'L' ? -1 : m == 'R' ? 1 : 0;
        r += dr; c += dc;
        if (visited.contains(r + "," + c)) {
            return new int[]{r, c};
        }
        visited.add(r + "," + c);
    }
    return null;
}

Line by line.

Line	What it does	Why
`visited = {(r, c)}`	The start counts as visited.	Otherwise returning to the start isn't noticed.
`if (r, c) in visited`	Been here before?	A tuple is hashable; a list wouldn't be.
`visited.add((r, c))`	Drop a pebble here.

Watch it run. Walk right, down, left, up from (0, 0).

Watch out for:

Storing positions as lists. Lists can't go in a Python set. Use tuples (or strings like "0,1" in TypeScript, where arrays compare by identity).

6. How to remember it

Memory hook: "The hand stamp"The gate only checks stamp or no stamp. A second stamp changes nothing. That's all a set knows, and it knows it instantly.

Picture

A queue at a festival gate, staff glancing at the back of each hand.

Chant

"In or out, no counting, no order."

Key rule

Checking membership in a list inside a loop? Make it a set first.

7. Problems solved with it

Three easy problems that are really one question: "is it in the set?"

LC 1496 · Path Crossing

The problemStarting at the origin, follow a path of moves N, S, E, W. Return true if you ever stand on a point you visited before.

What it doesOperation C, returning true or false.

CostO(n).

The code. A visited set of (x, y) points.

def is_path_crossing(path):
    x = y = 0
    visited = {(0, 0)}
    for m in path:
        if m == "N": y += 1
        elif m == "S": y -= 1
        elif m == "E": x += 1
        else: x -= 1
        if (x, y) in visited:
            return True
        visited.add((x, y))
    return False

function isPathCrossing(path: string): boolean {
  let x = 0, y = 0;
  const visited = new Set<string>(["0,0"]);
  for (const m of path) {
    if (m === "N") y += 1;
    else if (m === "S") y -= 1;
    else if (m === "E") x += 1;
    else x -= 1;
    if (visited.has(`${x},${y}`)) {
      return true;
    }
    visited.add(`${x},${y}`);
  }
  return false;
}

static boolean isPathCrossing(String path) {
    int x = 0, y = 0;
    Set<String> visited = new HashSet<>(List.of("0,0"));
    for (char m : path.toCharArray()) {
        if (m == 'N') y += 1;
        else if (m == 'S') y -= 1;
        else if (m == 'E') x += 1;
        else x -= 1;
        if (visited.contains(x + "," + y)) {
            return true;
        }
        visited.add(x + "," + y);
    }
    return false;
}

Line by line.

Line	What it does	Why
`visited = {(0, 0)}`	The origin is visited.	Returning to the start counts as crossing.
`if (x, y) in visited`	Stood here before?

Watch it run. Path "NESWW".

Watch out for:

Forgetting the starting point. Add (0, 0) before the first move.

LC 349 · Intersection of Two Arrays

The problemReturn the values that appear in both arrays, each once, in any order.

What it doesOperation B.

CostO(n + m).

The code. Python can do it in one line with &; the loop shows what that line does.

def intersection(nums1, nums2):
    in_first = set(nums1)
    result = set()
    for x in nums2:
        if x in in_first:
            result.add(x)
    return sorted(result)

function intersection(nums1: number[], nums2: number[]): number[] {
  const inFirst = new Set(nums1);
  const result = new Set<number>();
  for (const x of nums2) {
    if (inFirst.has(x)) {
      result.add(x);
    }
  }
  return [...result].sort((p, q) => p - q);
}

static List<Integer> intersection(int[] nums1, int[] nums2) {
    Set<Integer> inFirst = new HashSet<>();
    for (int x : nums1) inFirst.add(x);
    Set<Integer> result = new TreeSet<>();
    for (int x : nums2) {
        if (inFirst.contains(x)) {
            result.add(x);
        }
    }
    return new ArrayList<>(result);
}

Line by line.

Line	What it does	Why
`in_first = set(nums1)`	Membership in O(1).
`result.add(x)`	Each common value once.	The result is a set, so the second 2 changes nothing.

Watch it run. [1, 2, 2, 1] and [2, 2].

Watch out for:

Returning duplicates. Collect into a set, not a list.

LC 2215 · Find the Difference of Two Arrays

The problemReturn two lists: the distinct values of nums1 not in nums2, and the distinct values of nums2 not in nums1.

What it doesTwo set differences.

CostO(n + m).

The code. Turn both into sets, then keep what each has that the other lacks.

def find_difference(nums1, nums2):
    a, b = set(nums1), set(nums2)
    only_a = sorted(x for x in a if x not in b)
    only_b = sorted(x for x in b if x not in a)
    return [only_a, only_b]

function findDifference(nums1: number[], nums2: number[]): number[][] {
  const a = new Set(nums1), b = new Set(nums2);
  const onlyA = [...a].filter((x) => !b.has(x)).sort((p, q) => p - q);
  const onlyB = [...b].filter((x) => !a.has(x)).sort((p, q) => p - q);
  return [onlyA, onlyB];
}

static List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
    Set<Integer> a = new TreeSet<>(), b = new TreeSet<>();
    for (int x : nums1) a.add(x);
    for (int x : nums2) b.add(x);
    List<Integer> onlyA = new ArrayList<>(), onlyB = new ArrayList<>();
    for (int x : a) if (!b.contains(x)) onlyA.add(x);
    for (int x : b) if (!a.contains(x)) onlyB.add(x);
    return List.of(onlyA, onlyB);
}

Line by line.

Line	What it does	Why
`a, b = set(nums1), set(nums2)`	Distinct values of each.	Duplicates vanish here.
`x not in b`	In a but not in b.	O(1) per check.

Watch it run. [1, 2, 3, 3] and [1, 1, 2, 2].

Watch out for:

Forgetting the second list. The answer needs both directions.

More practice, solved on the pattern pages

#	Problem	Level	Where
217	Contains Duplicate	Easy	Solved step by step on 16 · Hash Map & Set
771	Jewels and Stones	Easy	Solved step by step on 16 · Hash Map & Set
219	Contains Duplicate II	Easy	Solved step by step on 03 · Sliding Window
128	Longest Consecutive Sequence	Medium	Solved step by step on 16 · Hash Map & Set
36	Valid Sudoku	Medium	Solved step by step on 16 · Hash Map & Set

8. Common mistakes

Searching a list in a loopif x in my_list is O(n) each time. Convert to a set once.

Expecting orderSets have no reliable order. Sort the result, or keep a separate list, when order matters.

Unhashable itemsLists and dicts can't go in a Python set. Use tuples or frozensets. In TypeScript, arrays are compared by identity, so store positions as strings.

Using a set when you need countsA set forgets how many times something appeared. Need "how many"? Use a hash map.

{} is not an empty setIn Python, {} is an empty dict. Write set().

9. Self-check quiz

A loop checks if x in banned, where banned is a list of 10,000 words. Best fix?

Each check drops from O(n) to O(1).

What is set([2, 1, 2, 1])?

Duplicates disappear; a set doesn't count.

Which can go into a Python set of visited grid cells?

Set items must be hashable: tuples are, lists and dicts aren't.

You need to know how many times each word appears. A set or a hash map?

A set only knows in or out.

10. Where it shows up next

16 · Hash Map & Set: duplicates, membership and the longest consecutive sequence.
11 · DFS and 12 · BFS: the visited set that stops a search walking in circles.
03 · Sliding Window: a set of what's inside the current window.
14 · Backtracking: a set of choices already used.

Next structure: 05 · Linked lists, where order is kept by pointers instead of positions.