What is the time complexity of Design HashSet?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Design HashSet?

This problem uses Array, Hash Table, Linked List, Design, Hash Function. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Design HashSet?

Insight 1: Since we can't use built-in hash table libraries, we need to choose an implementation strategy. One efficient approach is to use a boolean array (or a vector of booleans) due to the relatively small key range [0, 10^6]. Insight 2: Alternatively, we could use a separate chaining approach with a hash function and a list (or linked list) for each bucket to handle collisions. This approach is more space-efficient if the number of distinct keys is significantly smaller than the maximum possible key value.

Which companies ask LeetCode 705. Design HashSet in interviews?

This problem is frequently asked at Wix.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Design HashSet - LeetCode 705 Solution

Design HashSet - Complete Solution Guide

Design HashSet is LeetCode problem 705, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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,

Detailed Explanation

The problem requires you to implement a `MyHashSet` class that mimics the behavior of a HashSet data structure, without using built-in hash table libraries. A HashSet is a data structure that stores unique elements. The class should support three operations: `add(key)` to insert a key, `remove(key)` to delete a key, and `contains(key)` to check if a key exists in the set. The input `key` is a non-negative integer within the range [0, 10^6]. The number of calls to the methods is at most 10^4.

Solution Approach

The provided solutions implement the HashSet using different approaches. The Java and C++ solutions use a boolean array where the index represents the key, and the value represents whether the key is present in the set. The Python solution uses a simple hashing method with separate chaining. The C solution uses a dynamically allocated array to store the keys. When adding a key, we set the corresponding boolean array element to true (Java/C++). To remove, we set it to false. To check containment, we simply look up the value in the boolean array. The Python implementation uses a modulo operator for simple hashing to distribute keys into buckets, followed by adding, removing, or checking the list at the target bucket. The C implementation directly stores elements in an array, growing the array's capacity as needed.

Step-by-Step Algorithm

Step 1: Initialize the HashSet. For Java/C++, create a boolean array of size 1000001. For Python, create a list of lists (buckets). For C, allocate an array to store keys.
Step 2: `add(key)`: For Java/C++, set `array[key] = true`. For Python, calculate the index using `key % size`, and append the key to the list at `table[index]` if it's not already present. For C, add the key to the key array, reallocating the array if it's full.
Step 3: `remove(key)`: For Java/C++, set `array[key] = false`. For Python, calculate the index using `key % size`, and remove the key from the list at `table[index]` if it's present. For C, find the key in the keys array and replace it with the last element to effectively remove it.
Step 4: `contains(key)`: For Java/C++, return `array[key]`. For Python, calculate the index using `key % size`, and return `True` if the key is present in the list at `table[index]`, otherwise `False`. For C, iterate through the key array and return `True` if the key is found, `False` otherwise.
Step 5: `free()`: In the C implementation, free the dynamically allocated memory for the keys array, and then the HashSet object itself.

Key Insights

Insight 1: Since we can't use built-in hash table libraries, we need to choose an implementation strategy. One efficient approach is to use a boolean array (or a vector of booleans) due to the relatively small key range [0, 10^6].
Insight 2: Alternatively, we could use a separate chaining approach with a hash function and a list (or linked list) for each bucket to handle collisions. This approach is more space-efficient if the number of distinct keys is significantly smaller than the maximum possible key value.
Insight 3: Edge cases related to removing non-existent elements need to be handled to avoid errors or unexpected behavior.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Linked List, Design, Hash Function.

Companies

Asked at: Wix.

Design HashSet | LeetCode 705

Easy

Array Hash Table Linked List Design Hash Function

Time: O(n)Space: O(n)

Solution Code

Available in:

class MyHashSet {
    private boolean[] set;

    public MyHashSet() {
        set = new boolean[1000001];
    }

    public void add(int key) {
        set[key] = true;
    }

    public void remove(int key) {
        set[key] = false;
    }

    public boolean contains(int key) {
        return set[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);
 */

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 705: Design HashSet - Detailed explanation and solution approaches.

Topics

Array Hash Table Linked List Design Hash Function

Companies

Wix

Stats

Difficulty:Easy

Languages:4

Companies:1

Problem #:705

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Initialize the HashSet. For Java/C++, create a boolean array of size 1000001. For Python, create a list of lists (buckets). For C, allocate an array to store keys.
2
Step 2: `add(key)`: For Java/C++, set `array[key] = true`. For Python, calculate the index using `key % size`, and append the key to the list at `table[index]` if it's not already present. For C, add the key to the key array, reallocating the array if it's full.
3
Step 3: `remove(key)`: For Java/C++, set `array[key] = false`. For Python, calculate the index using `key % size`, and remove the key from the list at `table[index]` if it's present. For C, find the key in the keys array and replace it with the last element to effectively remove it.
4
Step 4: `contains(key)`: For Java/C++, return `array[key]`. For Python, calculate the index using `key % size`, and return `True` if the key is present in the list at `table[index]`, otherwise `False`. For C, iterate through the key array and return `True` if the key is found, `False` otherwise.
5
Step 5: `free()`: In the C implementation, free the dynamically allocated memory for the keys array, and then the HashSet object itself.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

Java and C++ solutions use a fixed-size boolean array, so all operations are direct array accesses, hence O(1). Python's separate chaining method has O(1) average time complexity for operations, but O(n) worst-case complexity if all keys collide in the same bucket. C solution uses an array, and since the search takes place within that array, each operation takes time linear to the number of keys stored in the set. Space complexity for Java and C++ is O(N) because of the fixed-size boolean array. The space complexity for Python is O(M) because the buckets store only the distinct keys inserted. C has a space complexity of O(M) due to storing all unique keys within an array.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Separate Chaining with Linked Lists

Use a hash function to map keys to indices in an array. Each index (bucket) contains a linked list of keys that hash to that index. This handles collisions effectively and is a classic hash table implementation.

Time: O(1) average case for add, remove, contains. O(n) worst-case, where n is the number of keys in a single bucket.Space: O(M), where M is the number of distinct keys stored.

Trade-offs: More space-efficient than using a large boolean array when the number of keys is much smaller than the maximum key value. More complex to implement due to the linked list management.

Using a Balanced Search Tree (e.g., Red-Black Tree)

Each bucket contains a balanced search tree (e.g. red-black tree), instead of a linked list. This guarantees a logarithmic time complexity for the basic operations.

Time: O(log n) where n is the number of keys in a single bucket.Space: O(M), where M is the number of distinct keys stored.

Trade-offs: Provides better worst-case time complexity guarantees, at the expense of higher constant factors and potentially increased code complexity.

✨

Key Insights

1Insight 1: Since we can't use built-in hash table libraries, we need to choose an implementation strategy. One efficient approach is to use a boolean array (or a vector of booleans) due to the relatively small key range [0, 10^6].
2Insight 2: Alternatively, we could use a separate chaining approach with a hash function and a list (or linked list) for each bucket to handle collisions. This approach is more space-efficient if the number of distinct keys is significantly smaller than the maximum possible key value.
3Insight 3: Edge cases related to removing non-existent elements need to be handled to avoid errors or unexpected behavior.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Linked List

Elements connected via pointers. Like a chain where each link knows the next.

Edge Cases

Edge case 1: Removing a non-existent key. The Python solution correctly handles this by attempting to remove the key from the list, which does nothing if the key isn't present. The Java and C++ solution sets the corresponding array element to `false`, which is also correct. The C implementation simply doesn't find the key in the array and does nothing.
Edge case 2: Adding the same key multiple times. The HashSet should only store unique keys. The Python solution correctly handles this by checking for the existence of the key before appending. The Java/C++ solutions overwrite the same element of the boolean array, resulting in only one instance of the key stored in the set. The C implementation checks if the element is already contained before adding.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to handle collisions when using separate chaining. If multiple keys map to the same index, you need a mechanism (like a linked list) to store them.

✗Common mistake 2: Using a hash function that doesn't distribute keys evenly. This can lead to many collisions and degrade performance.

✗Common mistake 3: Not resizing the hash table when it becomes too full (load factor is too high), which can also lead to increased collision rates and slower performance. (More relevant when implementing a fully featured hash table).

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Implementing a cache. A cache stores frequently accessed data for fast retrieval. A HashSet can be used to track which data is currently in the cache.

🏦Real-world scenario 2: Detecting duplicate entries in a database. A HashSet can be used to efficiently check if a new entry already exists.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Even for easy problems, discuss time and space complexity. Interviewers want to see you think analytically.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

👨‍💻 From Experience

This is one of the first problems I solved when learning Array. It's a great foundation for more complex problems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: November 13, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Design HashSet"?

For this easy-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?