Understand the concept
A list preserves order and can contain repeated values. A set holds unique, hashable values and does not promise list-like ordering. Use a list when sequence matters; use a set when you mainly need uniqueness or membership checks.
Big-O describes growth as input size n increases; it is not a stopwatch reading. Searching an unsorted list takes O(n) in the worst case. Set membership is O(1) on average under typical hashing behavior, with O(n) possible in the worst case. Building a set also costs time and memory.
If you make many membership checks, building one set may help. Rebuilding the set for every check wastes work. The code finds duplicate values and preserves the order in which each duplicate is first encountered. Its expected running time is O(n), and extra storage is O(n).
Run the example
def find_duplicates(values):
seen, reported = set(), set()
duplicates = []
for value in values:
if value in seen and value not in reported:
duplicates.append(value)
reported.add(value)
seen.add(value)
return duplicates
print(find_duplicates([3, 1, 3, 2, 1, 3]))Output / what to expect
[3, 1]Try it yourself
Write unique_in_order(values) for hashable values. Check [4, 2, 4, 1, 2]. Explain why list(set(values)) does not promise the same order.
View a suggested solution
def unique_in_order(values):
seen = set()
result = []
for value in values:
if value not in seen:
result.append(value)
seen.add(value)
return result
print(unique_in_order([4, 2, 4, 1, 2])) # [4, 2, 1]
# Sets do not provide a sequence-order guarantee.Reference: Official documentation ↗