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.