Write a function that returns all duplicate values in a list. What is the optimal time complexity?
The optimal solution is O(n) using a set to track seen elements and a second set to collect duplicates, avoiding any nested iteration. A Counter-based approach is equally O(n) and often more readable.
How to think about it
How to approach it
The first thing to say out loud is “I want O(n), not O(n²).” The naive nested-loop approach compares every pair — that’s quadratic and an instant red flag in interviews. The O(n) insight: use a hash set so membership checks cost O(1), and do a single pass.
There are two clean O(n) patterns worth knowing. Pick the one that fits — the two-set form is slightly faster at runtime; the Counter form is more readable when you also need counts.
Solution
Why the two-set form is slightly faster
The two-set form can short-circuit in the seen check — once a duplicate is found we don’t need to count further. The Counter always completes a full frequency pass. For very large inputs where duplicates appear early, two-sets wins on constant factors. In practice both are O(n) and either is acceptable in an interview.
The key insight
A hash set makes every membership check O(1). One pass through the list = O(n) total. Compare this to a sort-then-scan approach which is O(n log n) — sometimes acceptable, but never optimal.