Introduction

Finding a duplicate in linear time is usually straightforward if you are allowed extra memory. The standard solution is to scan the array once while tracking values you have already seen in a hash set. That gives average O(n) time and is the most practical answer for general input.

The General O(n) Solution

The idea is simple:

1. create an empty set
2. walk through the array once
3. if the current value is already in the set, you found a duplicate
4. otherwise add it and continue

Python example:

1def find_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
12print(find_first_duplicate([4, 1, 7, 3, 1, 9]))

This runs in linear time on average because set membership and insertion are average O(1) operations.

Returning All Duplicates

Sometimes the problem is not "find one duplicate" but "list all values that appear more than once". In that case, keep two sets:

• 'seen for values encountered at least once'
• 'duplicates for values confirmed to repeat'

1def find_all_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_all_duplicates([2, 5, 2, 3, 9, 5, 5, 1]))

This is still O(n) time, with O(n) extra space in the worst case.

Count Map Version

If you also need frequencies, use a hash map instead of a set:

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

This is useful when the consumer needs more than a yes-or-no answer.

Can You Do It in O(n) Time and O(1) Extra Space

Sometimes interview versions add stronger constraints, such as:

• array length is n + 1
• values are in the range 1 through n
• exactly one value is duplicated

Under those assumptions, there are specialized techniques. One famous example is Floyd's cycle detection, which treats the array like a linked structure and finds the repeated value in linear time with constant extra space.

1def find_duplicate_floyd(nums):
2    slow = nums[0]
3    fast = nums[0]
4
5    while True:
6        slow = nums[slow]
7        fast = nums[nums[fast]]
8        if slow == fast:
9            break
10
11    slow = nums[0]
12    while slow != fast:
13        slow = nums[slow]
14        fast = nums[fast]
15
16    return slow
17
18
19print(find_duplicate_floyd([1, 3, 4, 2, 2]))

This is elegant, but it only works because the input obeys a very specific structure. For arbitrary arrays, the hash-set solution is the correct default.

Why Sorting Is Usually Not the Best Answer

Another common idea is to sort the array and then scan neighboring elements. That works, but it changes the time complexity:

• sorting usually costs O(n log n)
• the scan after sorting is O(n)

So the total time is typically O(n log n), not O(n). It may still be acceptable in practice, but it does not satisfy the strict linear-time requirement.

Choosing the Right Approach

Use the hash-set solution when:

• input is arbitrary
• you want a simple implementation
• 'O(n) extra memory is acceptable'

Use a specialized constant-space technique only when the input guarantees are strong enough to support it. Otherwise, "clever" constant-space tricks often become wrong or fragile.

Common Pitfalls

The most common mistake is claiming an O(n log n) sorting solution is O(n) because the final scan is linear. The sort still dominates.

Another issue is ignoring input constraints. Floyd's cycle detection is excellent for the classic repeated-number problem, but it does not solve the general "find duplicates in any array" task. Developers also sometimes forget that hash-based O(1) operations are average-case assumptions, not strict worst-case guarantees.

Summary

• For general arrays, the standard linear-time solution uses a hash set.
• A set finds the first duplicate in average O(n) time with O(n) extra space.
• A map is useful when you need duplicate counts instead of only detection.
• Constant-space linear-time tricks require special input constraints.
• Sorting is often fine, but it is usually O(n log n), not true O(n).