algoadvance

Leetcode 705. Design HashSet

Problem Statement

Design a HashSet without using any built-in hash table libraries.

Implement MyHashSet class:

class MyHashSet {
    public MyHashSet();
    public void add(int key);
    public void remove(int key);
    public boolean contains(int key);
}

Clarifying Questions

1. Range of values: What is the range of keys that might be inserted into the HashSet?
   • Typically, integers range from -10^6 to 10^6.
2. Duplicates Handling: If we try to add an element that is already present, should it simply do nothing?
   • Yes, adding an already present element should have no effect.
3. Concurrency: Do we need to worry about thread safety for this implementation?
   • No, we can assume that the implementation does not need to be thread-safe.

Strategy

To implement a HashSet, we need to focus on three primary functionalities:

• Add an element: Insert an element into the set.
• Remove an element: Remove the element from the set if it exists.
• Check containment: Verify if an element is present in the set.

Given the constraints (e.g., value ranges), one simple and efficient way is to use a boolean array where the index represents the element.

1. Boolean Array Approach:
   • We assume key values range from 0 to 1,000,000 (non-negative only).
   • Create a boolean array of size 1,000,001 for quick direct addressing.
   • Index i in the array will represent the presence of the key i.

Code

Here’s how the implementation looks:

public class MyHashSet {

    private boolean[] set;
    
    public MyHashSet() {
        set = new boolean[1000001]; // Initializes the array to cover keys from 0 to 1,000,000
    }
    
    public void add(int key) {
        set[key] = true;
    }
    
    public void remove(int key) {
        set[key] = false;
    }
    
    public boolean contains(int key) {
        return set[key];
    }
}

Time Complexity

• Add Operation (add):
  • Time Complexity: O(1) because array indexing and assignment take constant time.
• Remove Operation (remove):
  • Time Complexity: O(1) because array indexing and assignment take constant time.
• Contains Operation (contains):
  • Time Complexity: O(1) because array indexing and value retrieval take constant time.

Thus, the solution provides O(1) time complexity for all operations, making it very efficient.

However, this solution uses extra space proportional to the range of keys we support (from 0 to 1,000,000), making its space complexity O(n), where n is the range of possible key values.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?