Python solution beats 85% time 80% memory with explanation
The brute force solution was to use an array of size 1000000 to track membership, and it works--but the space usage is a bit expensive(O(10^6) in best/worst/ave
The brute force solution was to use an array of size 1000000 to track membership, and it works--but the space usage is a bit expensive(O(10^6) in best/worst/average scenario), especially since most of the items in the range would never be touched.\nAs optimization, I used an array of 1000 --square root of 1000000. This way, the best case space complexity is O(10^3)/worst case is O(10^6). For hash function I simply used `key % 1000`.\n```\nclass MyHashSet:\n\n    def __init__(self):\n        """\n        Initialize your data structure here.\n        """\n        self.arr = [[] for i in range(1000)]\n    \n    def hash(self, key:int):\n        return key % 1000\n\n    def add(self, key: int) -> None:\n        hashKey = self.hash(key)\n        if not self.contains(key):\n            self.arr[hashKey].append(key)\n\n    def remove(self, key: int) -> None:\n        hashKey = self.hash(key)\n        if self.contains(key):\n            self.arr[hashKey].remove(key)\n\n    def contains(self, key: int) -> bool:\n        """\n        Returns true if this set contains the specified element\n        """\n        hashKey = self.hash(key)\n        return key in self.arr[hashKey]\n```\nFurther optimization ideas:\n* You can use a linked list instead of array to implement hash collisions--can reduce the insertion/removal time.\n* In hash collision table you can store `key//1000` instead of `key` since the last 3 digits should be the same for the same hash key--can reduce the space needed although the big O space complexity would be the same.
[]