Design HashSet

Problem

Design a class MyHashSet storing ints in 0..10⁶. Implement add(int), remove(int), and contains(int) returning a boolean.

Constraints

• 0 ≤ key ≤ 10⁶

Approach — Hashing & Counting

This is a Hashing & Counting problem. The idea: store what you've seen in a hash map for O(1) lookups, trading a little space to avoid a nested scan. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class MyHashSet:
    def __init__(self):
        self.size = 1000
        self.buckets = [[] for _ in range(self.size)]

    def add(self, key):
        b = self.buckets[key % self.size]
        if key not in b:
            b.append(key)

    def remove(self, key):
        b = self.buckets[key % self.size]
        if key in b:
            b.remove(key)

    def contains(self, key):
        return key in self.buckets[key % self.size]

Java

class MyHashSet {
    private boolean[] data = new boolean[1000001];
    public void add(int key) { data[key] = true; }
    public void remove(int key) { data[key] = false; }
    public boolean contains(int key) { return data[key]; }
}

class Solution {}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.