Introduction

This problem usually has a specific structure: the array has size n + 2, the values are supposed to be in the range 1 through n, and exactly two values appear twice. That structure is important because it enables better solutions than a generic duplicate search.

There are several ways to solve it. The easiest to understand uses a set. More interview-oriented solutions use math or bit manipulation to reduce extra space.

A Simple Set-Based Solution

If you want the most straightforward correct answer, keep track of seen values and collect duplicates.

1def find_two_repeats(nums):
2    seen = set()
3    repeats = []
4
5    for value in nums:
6        if value in seen:
7            repeats.append(value)
8        else:
9            seen.add(value)
10
11    return repeats
12
13
14arr = [4, 2, 4, 5, 2, 3, 1]
15print(find_two_repeats(arr))

This prints:

[4, 2]

Time complexity is O(n) and extra space is O(n). For production code, this is often the best tradeoff because it is easy to verify and hard to get wrong.

A Sorting-Based Approach

Sorting also works. After sorting, duplicates become adjacent.

1def find_two_repeats_sorted(nums):
2    values = sorted(nums)
3    repeats = []
4
5    for i in range(1, len(values)):
6        if values[i] == values[i - 1]:
7            repeats.append(values[i])
8
9    return repeats
10
11
12arr = [4, 2, 4, 5, 2, 3, 1]
13print(find_two_repeats_sorted(arr))

This is easy to explain, but it costs O(n log n) time because of the sort. It is still perfectly acceptable when the input is not huge and simplicity matters more than optimal asymptotic performance.

Using XOR for O(1) Extra Space

The more interesting solution uses the structure of the problem. Since numbers should be from 1 to n and only two numbers repeat, you can XOR:

• all array elements
• with all integers from 1 to n

Everything that appears once cancels out, leaving x ^ y, where x and y are the repeating numbers.

Then split values into two groups using a set bit and XOR again.

1def find_two_repeats_xor(nums):
2    n = len(nums) - 2
3    xor_all = 0
4
5    for value in nums:
6        xor_all ^= value
7
8    for value in range(1, n + 1):
9        xor_all ^= value
10
11    rightmost_set_bit = xor_all & -xor_all
12
13    x = 0
14    y = 0
15
16    for value in nums:
17        if value & rightmost_set_bit:
18            x ^= value
19        else:
20            y ^= value
21
22    for value in range(1, n + 1):
23        if value & rightmost_set_bit:
24            x ^= value
25        else:
26            y ^= value
27
28    return [x, y]
29
30
31arr = [4, 2, 4, 5, 2, 3, 1]
32print(find_two_repeats_xor(arr))

This solution runs in O(n) time and uses O(1) extra space. It is a strong interview answer because it shows you understand how XOR cancels matched values.

Why the XOR Trick Works

Suppose the array contains all numbers from 1 to n, except two of them appear twice. If you XOR the full array with the clean sequence 1 through n, every non-repeated number appears twice overall and cancels out.

That leaves:

x ^ y

where x and y are the two repeated numbers. Once you isolate any bit where x and y differ, you can separate the values into two groups and recover each one independently.

This method is elegant, but it is easier to misuse than the set-based solution, so it is best when the input guarantees are trustworthy.

When Input Constraints Matter

The constant-space tricks only work because the array follows the exact rules:

• size is n + 2
• values are in the range 1 through n
• exactly two numbers repeat

If those assumptions are not guaranteed, the XOR or arithmetic approaches become unsafe. In that case, use a dictionary or set instead of forcing a specialized algorithm onto a more general problem.

Common Pitfalls

One common mistake is forgetting that the problem is not “find all duplicates in any array.” The clever constant-space methods depend completely on the 1 through n structure.

Another mistake is implementing the XOR approach without understanding why the partition step works. That often produces code that looks clever but is hard to debug.

Sorting can also introduce an accidental bug if you mutate an input array the caller expected to remain unchanged. If that matters, sort a copy instead.

Finally, the set-based solution is often the right real-world answer even if it is not the most mathematically interesting one. Readability is usually worth more than saving a small amount of memory unless the problem explicitly demands it.

Summary

• The simplest solution uses a set and runs in O(n) time with O(n) extra space.
• Sorting also works but costs O(n log n) time.
• The XOR method gives O(n) time and O(1) extra space when the input constraints are exact.
• Choose the constant-space trick only when the array truly follows the 1 through n problem structure.
• In production code, prefer the clearest correct solution unless memory constraints are the real bottleneck.

1. Sort the array.
2. Traverse the sorted array to find consecutive duplicates.

Complexity Analysis:

• Time Complexity: O(n log n), due to the sorting operation.
• Space Complexity: O(1) if in-place sorting is used, otherwise O(n).

Example:

• Time Complexity: O(n), traversing the array and hash map operations.
• Space Complexity: O(n), due to the hash map.
  • Sum of duplicates equation: $x + y = S_actual - S_n$
  • Sum of squares of duplicates equation: $x^2 + y^2 = S2_actual - S2_n$
• Time Complexity: O(n), for computing sums.
• Space Complexity: O(1).
• Time Complexity: O(n), for single-pass operations.
• Space Complexity: O(1).