Introduction

Finding duplicates in an integer array is a classic problem, but the best solution depends on the constraints. If you only want a correct and readable answer, a hash set is usually the right tool. If memory is tight or the input has special structure, other techniques may be better.

That is why "find the duplicate" is not really one algorithmic question. It is a family of questions with different tradeoffs around time, space, and whether the input may be modified.

The Straightforward Hash-Set Solution

For general-purpose code, the simplest efficient approach is to track numbers already seen:

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 sorted(duplicates)
12
13
14print(find_duplicates([4, 5, 6, 1, 4, 2, 6]))  # [4, 6]

This solution is popular because it is:

• easy to understand
• 'O(n) average time'
• correct for arbitrary integer values

The tradeoff is extra memory for the set.

Sorting When Extra Memory Must Stay Small

If modifying the array is allowed, sorting can reduce auxiliary memory:

1def find_duplicates_sorted(values):
2    values = sorted(values)
3    duplicates = []
4
5    for i in range(1, len(values)):
6        if values[i] == values[i - 1]:
7            if not duplicates or duplicates[-1] != values[i]:
8                duplicates.append(values[i])
9
10    return duplicates
11
12
13print(find_duplicates_sorted([4, 5, 6, 1, 4, 2, 6]))  # [4, 6]

This uses O(n log n) time because of the sort. It is slower than the hash-set approach on average, but sometimes that tradeoff is acceptable when memory pressure matters more.

Special Case: One Duplicate Under Range Constraints

Some interview-style versions of the problem come with strong guarantees:

• array length is n + 1
• values are in the range 1 through n
• exactly one value is duplicated, possibly more than once

That version can be solved with Floyd's cycle detection in O(1) extra space, but it is not a general duplicate-finding algorithm. It relies on the range constraints to interpret values as pointers.

So unless the problem statement includes those guarantees explicitly, do not force that technique onto a normal array problem.

Decide What "Duplicate" Means

You should also clarify the required output:

• return the first duplicate encountered
• return all duplicated values
• return every repeated occurrence
• return counts of each repeated value

These are different tasks. For example, if you need counts, a frequency map is more direct:

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

The algorithm you choose should match the exact output shape, not just the word "duplicate."

Mutating the Input Is a Real Tradeoff

Sorting is fine when a copied or reordered array is acceptable. It is a bad idea when:

• the original order matters
• the array is shared elsewhere
• mutation would surprise callers

In those cases, the hash-set solution is often the safer choice even if it uses extra space.

Common Pitfalls

• Choosing a specialized constant-space trick for a problem that does not satisfy its range constraints.
• Forgetting to define whether the goal is one duplicate, all duplicates, or duplicate counts.
• Sorting in place without realizing the original order was important.
• Adding the same duplicate multiple times instead of deduplicating the output.
• Over-optimizing an easy O(n) hash-set problem into something harder to read without a real need.

Summary

• For the general case, a hash set is usually the clearest efficient solution.
• Sorting is a good alternative when modifying or copying the array is acceptable.
• Constant-space tricks only apply to special constrained versions of the problem.
• Clarify whether you need one duplicate, all duplicates, or counts.
• Let the input constraints drive the algorithm choice instead of forcing one favorite technique everywhere.