A set is a collection of elements with no duplicates. To implement it, we need APIs for adding, removing, looking up, clearing, and iterating through each element. Sets can be implemented in various ways. It can be implemented using maps or using lists.
Below is a sample implementation of sets using maps:
In this implementation, add(), remove(), and lookup() functions have a time complexity of O(1). However, the clear() and iterate() functions have a time complexity of O(N), where N represents the maximum number of elements. As these functions iterate over a loop of MAX elements, the time complexity is the same even if the actual number of elements in the set is lower.
One way to reduce the time complexity of clear() and iterate() lists can be used. Here’s is the sample implementation of sets using lists:
Here in this implementation, iterate(), clear() functions time complexity is reduced to O(count) where the count is the number of elements in the set. But the time complexity of add(), remove() and lookup() increased to O(count).
So how to get the best implementation where the add(), remove() and lookup() functions should have O(1) time complexity and iterate(), clear() functions have the time complexity of O(count).
This is a bit tricky. For the time complexity of O(1) for add(), remove() and lookup() functions, implementation should support maps[] and for the time complexity of O(count) for clear() and iterate() functions, implementation should support lists. So for the best performance, implementation should support maps and list. If we maintain both maps and list , how do we synchronize these two by not increasing the time complexity. This is the challenging stuff here.
There should not be any loop in add(), remove(), lookup() functions to update list[]. clear() and iterate() should not go over maps[].
So how to synchronise and implement it.
I will write this in my next post. Please think and comment.
