TypeScript: No hash table libraries or generic objects used.
Intuition\nThe code implements a simple HashSet data structure using open addressing with linear probing to handle collisions. The HashSet allows adding, removi
# Intuition\nThe code implements a simple HashSet data structure using open addressing with linear probing to handle collisions. The HashSet allows adding, removing, and checking for the existence of elements in a collection. The crucial aspect of this implementation is the usage of prime numbers for the size of the underlying array to reduce the likelihood of collisions.\n\n# Approach\nThe HashSet class uses an array to store elements, and the elements are inserted into the array using a hash function to determine the appropriate index. If there is a collision (i.e., the index is already occupied), linear probing is used to find the next available index for insertion. If the load factor (ratio of elements to array size) becomes too high (>= 75%), the array is rehashed with a larger size to reduce collisions.\n\nThe add method inserts an element into the HashSet. It computes the hash value using the hash function and resolves collisions using linear probing. If the load factor becomes high, the method triggers a rehash operation to resize the array.\nThe remove method removes an element from the HashSet. It searches for the element using the hash function and removes it from the array.\nThe contains method checks if an element exists in the HashSet. It follows the same process of computing the hash value and probing linearly until it finds the element or reaches an empty slot.\n\n# Complexity\n- Time complexity:\nThe time complexity of adding, removing, and checking the existence of an element in the HashSet is generally O(1). However, in the worst-case scenario of many collisions, the time complexity can approach O(n), where n is the number of elements in the HashSet.\n\n- Space complexity:\nThe space complexity is O(n), where n is the number of elements in the HashSet. Additionally, there is extra space used for the array and other variables, but their sizes are constant, so they do not affect the overall space complexity\n\n# Code\n```\nclass MyHashSet {\n    // An array of prime numbers used to determine the size of the internal array\n    primes = [53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869]\n    \n    // The current size of the hash set (number of elements)\n    size = 0;\n\n    // The index used to access the prime number for the current internal array\n    i = 0;\n\n    // The internal array representing the hash set, initialized with undefined values\n    arr = Array(this.primes[this.i]).fill(undefined);\n\n    constructor() {\n        // The constructor is empty as initialization is already done above.\n    }\n\n    // Adds a key to the hash set\n    add(key: number): void {\n        let hashKey = this.hash(key);\n        let firstNegOne = -1;\n\n        // While the current position in the internal array is occupied and not the key we\'re looking for\n        // Keep probing for the next available position using linear probing\n        while(this.arr[hashKey] !== undefined && this.arr[hashKey] !== key){\n            // Keep track of the first position with value -1 (previously removed element)\n            if(this.arr[hashKey] === -1 && firstNegOne === -1){\n                firstNegOne = hashKey;\n            }\n            hashKey = (hashKey + 1) % this.primes[this.i];\n        }\n\n        // If a position with value -1 was found, use it for the new key\n        // Otherwise, if the position is still undefined, store the new key there\n        if(this.arr[hashKey] === undefined && firstNegOne !== -1){\n            this.size++;\n            this.arr[firstNegOne] = key;\n        } else if(this.arr[hashKey] === undefined){\n            this.size++;\n            this.arr[hashKey] = key;\n        }\n\n        // Check if the hash set has exceeded the load factor (75%)\n        // If so, trigger a rehash to increase the internal array size and reduce collisions\n        if((this.size / this.primes[this.i]) * 100 >= 75){\n            this.rehash();\n        }\n    }\n\n    // Removes a key from the hash set\n    remove(key: number): void {\n        let hashKey = this.hash(key);\n\n        // While the current position in the internal array is occupied and not the key we\'re looking for\n        // Keep probing for the next position to find the key to remove\n        while(this.arr[hashKey] !== undefined && this.arr[hashKey] !== key){\n            hashKey = (hashKey + 1) % this.primes[this.i];\n        }\n\n        // If the key is found at the current position, remove it from the hash set by setting it to -1\n        if(this.arr[hashKey] === key){\n            this.size--;\n            // Need to set it to -1 for the contains function.\n            // If we set it to undefined then the contains function might exit earlier than its needed.\n            this.arr[hashKey] = -1;\n        }\n    }\n\n    // Checks if the hash set contains a given key\n    contains(key: number): boolean {\n        let hashKey = this.hash(key);\n\n        // While the current position in the internal array is occupied and not the key we\'re looking for\n        // Keep probing for the next position to check if the key exists in the hash set\n        while(this.arr[hashKey] !== undefined && this.arr[hashKey] !== key){\n            hashKey = (hashKey + 1) % this.primes[this.i];\n        }\n\n        // Return true if the key is found in the hash set (i.e., the position is not undefined)\n        // Otherwise, return false\n        return this.arr[hashKey] !== undefined ? true : false;\n    }\n\n    // Rehashes the hash set, increasing the size of the internal array and redistributing the keys\n    rehash(): void{\n        this.i++;\n        \n        // Store the old internal array in a temporary variable\n        let oldArray = this.arr;\n        // Create a new internal array with the next prime size\n        this.arr = Array(this.primes[this.i]).fill(undefined);\n        // Reset the size counter\n        this.size = 0;\n\n        // Re-insert all non-removed keys from the old internal array into the new array\n        for(let i = 0; i < oldArray.length; i++){\n            if(oldArray[i] !== undefined && oldArray[i] !== -1){\n                this.add(oldArray[i]);\n            }\n        }\n    }\n\n    // Hash function that maps a key to an index in the internal array\n    hash(key: number): number{\n        return key % this.primes[this.i];\n    }\n\n}\n```
['Array', 'Hash Table', 'Dynamic Programming', 'Hash Function', 'TypeScript']