Find Duplicate Items in a List in O(N) Time in Python

Question

Given a list of customer IDs, find all IDs that appear more than once. Return the duplicates in deterministic sorted order.

Accepted Answer

Optimal Solution:
def find_duplicates(items: list[int]) -> list[int]:
    seen = set()
    duplicates = set()
    for item in items:
        if item in seen:
            duplicates.add(item)
        else:
            seen.add(item)
    return sorted(duplicates)

Technical Explanation:
Tracking visited items in a `seen` set allows detecting repeat items in O(1) time per item. Adding duplicates to a `duplicates` set prevents counting the same duplicate repeatedly.