Hash set

Overview

A hash set stores unique values and answers 'have I seen this?' in O(1) on average. It is a hash map with keys only. Adding a value that already exists has no effect.

Sets are the simplest way to remove duplicates, check membership, and compute intersections and unions. Many O(n^2) 'does it exist' loops become O(n) by putting one side into a set.

When to use it

• Detecting duplicates or cycles (visited states).
• Fast membership tests: is this word in the dictionary?
• Removing duplicates while preserving first occurrence.
• Set algebra: intersection, union, difference.
• Visited tracking in BFS and DFS.

Problem patterns it solves

Where it is used in real software

Key terms

add

Insert a value; no effect if already present. O(1) average.

has / contains

Membership test. O(1) average.

delete / remove

Remove a value. O(1) average.

Bloom filter

Probabilistic set: no false negatives, small chance of false positives, very little memory.

Using a set effectively

1. 1
   Decide what identity means

   Numbers and strings compare by value. For pairs or coordinates, encode a string key like `${r},${c}` in JS, or use a record in Java.

2. 2
   Check before adding when you need to detect repeats

   if (set.has(x)) duplicate found; else set.add(x).

3. 3
   Build from an array for membership tests

   new Set(arr) is O(n); every later has() is O(1).

4. 4
   Remove values to maintain a window

   In sliding window problems, delete the value leaving the window.

Happy number cycle detection

n = 2: replace n with the sum of the squares of its digits

4 repeats, so the process loops forever without reaching 1. The set detects the cycle in O(number of states); Floyd's fast and slow pointers can do it with O(1) space.

Implementation

1const containsDuplicate = (nums) => new Set(nums).size !== nums.length;2 3// 219: duplicate within distance k (set as a sliding window)4function containsNearbyDuplicate(nums, k) {5  const window = new Set();6  for (let i = 0; i < nums.length; i++) {7    if (window.has(nums[i])) return true;8    window.add(nums[i]);9    if (window.size > k) window.delete(nums[i - k]);10  }11  return false;12}13 14function isHappy(n) {15  const seen = new Set();16  while (n !== 1 && !seen.has(n)) {17    seen.add(n);18    let next = 0;19    while (n > 0) {20      const d = n % 10;21      next += d * d;22      n = Math.floor(n / 10);23    }24    n = next;25  }26  return n === 1;27}28 29// Set algebra30const a = new Set([1, 2, 3]), b = new Set([2, 3, 4]);31const intersection = [...a].filter((x) => b.has(x)); // [2, 3]32const union = new Set([...a, ...b]);                 // {1, 2, 3, 4}33const difference = [...a].filter((x) => !b.has(x));  // [1]34 35// Coordinates: encode as strings36const visited = new Set();37visited.add(`${2},${3}`);

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Adding arrays or objects to a JS Set and expecting value equality.

  Fix: Sets compare objects by reference. Encode them as strings or numbers first.

• Using a set when counts matter.

  Fix: Use a map of counts when duplicates must be counted.

• Iterating a set while deleting in Java.

  Fix: Use an Iterator's remove(), or collect items to remove first.

Interview questions

Practice problems