Introduction

Finding duplicates in an unsorted sequence is a classic interview and production problem. The best approach depends on what “find duplicates” means in your case: detect whether any duplicate exists, return the duplicate values, or count how many times each value appears.

Because the input is unsorted, you cannot rely on adjacent comparisons unless you sort first. In most real programs, a hash-based approach is the simplest and fastest option.

Use a Set for One-Pass Detection

If you only need to know which values appear more than once, a set gives an efficient one-pass solution. As you scan the sequence, keep one set for items you have seen and another set for items already confirmed as duplicates.

1def find_duplicates(values):
2    seen = set()
3    duplicates = set()
4
5    for value in values:
6        if value in seen:
7            duplicates.add(value)
8        else:
9            seen.add(value)
10
11    return duplicates
12
13
14items = [5, 3, 9, 5, 2, 3, 8, 3]
15print(find_duplicates(items))

{3, 5}

This runs in average O(n) time because set membership checks are usually constant time. The tradeoff is memory: you store up to all distinct values, so the extra space is O(n).

This approach is a good default when:

• order does not matter
• you only care about repeated values
• the values are hashable

Count Frequencies When You Need More Detail

Sometimes just knowing that 3 is duplicated is not enough. You may need counts so you can answer questions like “which values appear at least twice?” or “what is the most common value?” In that case, use a dictionary or collections.Counter.

1from collections import Counter
2
3
4def duplicate_counts(values):
5    counts = Counter(values)
6    return {value: count for value, count in counts.items() if count > 1}
7
8
9items = ["apple", "pear", "apple", "banana", "pear", "pear"]
10print(duplicate_counts(items))

{'apple': 2, 'pear': 3}

If you prefer not to import Counter, the manual version is still straightforward:

1def duplicate_counts_manual(values):
2    counts = {}
3
4    for value in values:
5        counts[value] = counts.get(value, 0) + 1
6
7    duplicates = {}
8    for value, count in counts.items():
9        if count > 1:
10            duplicates[value] = count
11
12    return duplicates

This is still average O(n) time with O(n) extra space. The main benefit over the pure set version is that it preserves frequency information.

Sort When Memory Matters More Than Speed

If extra memory is tight and mutating the input is acceptable, sorting can help. Once the sequence is sorted, duplicates become neighbors and are easy to detect with a linear pass.

1def find_duplicates_sorted(values):
2    values = sorted(values)
3    duplicates = set()
4
5    for index in range(1, len(values)):
6        if values[index] == values[index - 1]:
7            duplicates.add(values[index])
8
9    return duplicates
10
11
12items = [7, 1, 4, 1, 9, 7, 7]
13print(find_duplicates_sorted(items))

{1, 7}

The full cost is O(n log n) because of sorting. You often use less auxiliary memory than the hash-based version, but you lose the original order unless you sort a copy. That makes this method useful when memory pressure is real or when the data is already sorted as part of another pipeline step.

Return the First Duplicate Seen

A slightly different problem is returning the first duplicate encountered during a left-to-right scan. This shows up in validation logic and streaming systems.

1def first_duplicate(values):
2    seen = set()
3
4    for value in values:
5        if value in seen:
6            return value
7        seen.add(value)
8
9    return None
10
11
12items = [10, 4, 2, 8, 4, 10]
13print(first_duplicate(items))

4

This solution is also average O(n) time and is often all you need when a duplicate should trigger an early failure.

Streaming and Large Inputs

For very large inputs, the key question is whether all data fits in memory. If it does not, exact duplicate detection becomes harder because hash-based approaches need to remember what has been seen. Common strategies include chunking, external sorting, or using a database table with a unique index and then checking violations.

In normal in-memory application code, though, a set or frequency map remains the most practical answer. The bottleneck is usually not the duplicate-check logic itself, but the cost of materializing and storing the input.

Common Pitfalls

One common mistake is using the brute-force nested-loop approach by default. It is easy to write, but O(n^2) time becomes expensive fast.

Another issue is forgetting that sets and dictionary keys require hashable values. Lists and other mutable containers cannot be added directly. If your elements are compound records, convert them to tuples or extract a stable key first.

Sorting can also introduce bugs when callers expect the original order to stay untouched. Use sorted(values) instead of values.sort() if you need to preserve the source data.

Finally, be precise about the output you want. “Find duplicates” can mean a boolean answer, a list of repeated values, counts, or the first repeated item in scan order. Choosing the wrong interpretation often leads to extra work or incorrect results.

Summary

• A hash set gives the usual best answer for duplicate detection in an unsorted sequence.
• Use Counter or a dictionary when you need frequencies, not just repeated values.
• Sorting is a reasonable fallback when memory is more constrained than CPU time.
• Define the required result clearly before coding: any duplicate, all duplicates, counts, or first duplicate.
• For large real-world datasets, memory usage often matters more than the asymptotic lookup cost.