Sean Sean - 1 month ago 8
Python Question

Python: Elegant way to store items for checking item existence in a container

In the situation I encounter, I would like to define "elegant" being having 1) constant O(1) time complexity for checking if an item exists and 2) store only items, nothing more.

For example, if I use a list

num_list = []
for num in range(10): # Dummy operation to fill the container.
num_list += num
if 1 in num_list:
print("Number exists!")


The operation "in" will take O(n) time according to [Link]

In order to achieve constant checking time, I may employ a dictionary

num_dict = {}
for num in range(10): # Dummy operation to fill the container.
num_dict[num] = True
if 1 in num_dict:
print("Number exists!")


In the case of a dictionary, the operation "in" costs O(1) time according to [Link], but additional O(n) storage is required to store dummy values. Therefore, both implementations/containers seem inelegant.

What would be a better implementation/container to achieve constant O(1) time for checking if an item exists while only storing the items? How to keep resource requirement to the bare minimum?

Answer

The solution here is to use a set, which doesn╦łt requires you to save a dummy variable for each value.