Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Build confidence with an intuition-first walkthrough focused on array fundamentals.
Design a HashSet without using any built-in hash table libraries.
Implement MyHashSet class:
void add(key) Inserts the value key into the HashSet.bool contains(key) Returns whether the value key exists in the HashSet or not.void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.Example 1:
Input ["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"] [[], [1], [2], [1], [3], [2], [2], [2], [2]] Output [null, null, null, true, false, null, true, null, false] Explanation MyHashSet myHashSet = new MyHashSet(); myHashSet.add(1); // set = [1] myHashSet.add(2); // set = [1, 2] myHashSet.contains(1); // return True myHashSet.contains(3); // return False, (not found) myHashSet.add(2); // set = [1, 2] myHashSet.contains(2); // return True myHashSet.remove(2); // set = [1] myHashSet.contains(2); // return False, (already removed)
Constraints:
0 <= key <= 106104 calls will be made to add, remove, and contains.Problem summary: Design a HashSet without using any built-in hash table libraries. Implement MyHashSet class: void add(key) Inserts the value key into the HashSet. bool contains(key) Returns whether the value key exists in the HashSet or not. void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map · Linked List · Design
["MyHashSet","add","add","contains","contains","add","contains","remove","contains"] [[],[1],[2],[1],[3],[2],[2],[2],[2]]
design-hashmap)design-skiplist)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #705: Design HashSet
class MyHashSet {
private boolean[] data = new boolean[1000001];
public MyHashSet() {
}
public void add(int key) {
data[key] = true;
}
public void remove(int key) {
data[key] = false;
}
public boolean contains(int key) {
return data[key];
}
}
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet obj = new MyHashSet();
* obj.add(key);
* obj.remove(key);
* boolean param_3 = obj.contains(key);
*/
// Accepted solution for LeetCode #705: Design HashSet
type MyHashSet struct {
data []bool
}
func Constructor() MyHashSet {
data := make([]bool, 1000010)
return MyHashSet{data}
}
func (this *MyHashSet) Add(key int) {
this.data[key] = true
}
func (this *MyHashSet) Remove(key int) {
this.data[key] = false
}
func (this *MyHashSet) Contains(key int) bool {
return this.data[key]
}
/**
* Your MyHashSet object will be instantiated and called as such:
* obj := Constructor();
* obj.Add(key);
* obj.Remove(key);
* param_3 := obj.Contains(key);
*/
# Accepted solution for LeetCode #705: Design HashSet
class MyHashSet:
def __init__(self):
self.data = [False] * 1000001
def add(self, key: int) -> None:
self.data[key] = True
def remove(self, key: int) -> None:
self.data[key] = False
def contains(self, key: int) -> bool:
return self.data[key]
# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)
// Accepted solution for LeetCode #705: Design HashSet
/*
* @lc app=leetcode id=705 lang=rust
*
* [705] Design HashSet
*/
use std::vec;
// @lc code=start
struct MyHashSet {
buckets: Vec<Vec<i32>>,
capacity: usize,
size: usize,
load_factor: f64,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl MyHashSet {
fn new() -> Self {
Self {
buckets: vec![Vec::new(); 8],
capacity: 8,
size: 0,
load_factor: 0.75,
}
}
fn hash(&self, key: i32) -> usize {
(key % self.capacity as i32) as usize
}
fn add(&mut self, key: i32) {
let index = self.hash(key);
let bucket = &mut self.buckets[index];
if !bucket.iter().any(|&k| k == key) {
bucket.push(key);
self.size += 1;
if self.size as f64 / self.capacity as f64 > self.load_factor {
self.resize()
}
}
}
fn remove(&mut self, key: i32) {
let index = self.hash(key);
let bucket = &mut self.buckets[index];
if let Some(i) = bucket.iter().position(|&k| k == key) {
bucket.swap_remove(i);
self.size -= 1;
}
}
fn contains(&self, key: i32) -> bool {
let index = self.hash(key);
let bucket = &self.buckets[index];
bucket.iter().any(|&k| k == key)
}
fn resize(&mut self) {
let new_capacity = self.capacity * 2;
let mut new_buckets = vec![Vec::new(); new_capacity];
for bucket in self.buckets.iter() {
for &key in bucket.iter() {
let new_index = (key % new_capacity as i32) as usize;
new_buckets[new_index].push(key);
}
}
self.buckets = new_buckets;
self.capacity = new_capacity;
}
}
// @lc code=end
// Accepted solution for LeetCode #705: Design HashSet
class MyHashSet {
data: Array<boolean>;
constructor() {
this.data = new Array(10 ** 6 + 1).fill(false);
}
add(key: number): void {
this.data[key] = true;
}
remove(key: number): void {
this.data[key] = false;
}
contains(key: number): boolean {
return this.data[key];
}
}
/**
* Your MyHashSet object will be instantiated and called as such:
* var obj = new MyHashSet()
* obj.add(key)
* obj.remove(key)
* var param_3 = obj.contains(key)
*/
Use this to step through a reusable interview workflow for this problem.
Copy all n nodes into an array (O(n) time and space), then use array indexing for random access. Operations like reversal or middle-finding become trivial with indices, but the O(n) extra space defeats the purpose of using a linked list.
Most linked list operations traverse the list once (O(n)) and re-wire pointers in-place (O(1) extra space). The brute force often copies nodes to an array to enable random access, costing O(n) space. In-place pointer manipulation eliminates that.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.