How do you detect whether an array contains a duplicate value, and what is the space trade-off?
You keep a set of the values you have already seen, and when you meet one that is already in the set you have found a duplicate.
def contains_duplicate(values):
seen = set()
for value in values:
if value in seen:
return True
seen.add(value)
return False
So how does it work? The set starts empty. For each value you ask whether it is already in the set. If it is then you have seen this value before, so the answer is yes and you stop. If it is not then you add it, so that the next time you meet the same value you will catch it.
And the space trade-off is this. The set can grow as big as the list, so the space is O of n in the worst case, where n is the number of values. The time is O of n, because you go through the list once and each check in the set is quick.
And there is an early exit worth knowing about. The function returns as soon as it finds a duplicate, so on a list where the duplicate is near the front it stops early. In the worst case, where the duplicate is at the very end or there is no duplicate at all, it goes through the whole list.
So when is a set the right tool? When you need the answer and you do not mind using extra memory. The space is the price you pay for the speed.
And when is it the wrong tool? When the memory is tight, because the set can be as big as the list itself.
The next question in this topic shows the version that uses no extra memory at all.