N-Repeated Element in Size 2N Array

N-Repeated Element in Size 2N Array

What is this problem about?

The N-Repeated Element in Size 2N Array problem gives you an array of size 2N containing N+1 unique values — all values appear exactly once except one value that appears exactly N times. Find the N-repeated element. This easy coding problem has multiple O(n) solutions leveraging the high frequency of the repeated element.

Why is this asked in interviews?

Akamai and Google ask this simple problem to quickly assess whether candidates can reason about element frequencies. With N repetitions out of 2N elements, the repeated element is extremely dense. The array and hash table interview pattern is straightforward here, but the problem also has elegant O(1) space solutions.

Algorithmic pattern used

Hash set or pigeonhole observation. Hash set approach: traverse the array; return the first element seen twice. Pigeonhole: with N elements repeated among 2N positions, check every pair arr[i] == arr[i+1] or arr[i] == arr[i+2]. The repeated element must appear adjacent or within 2 positions due to pigeonhole principle.

Example explanation

Array: [2, 1, 3, 2, 2, 2]. N=3, size=6. The element 2 appears 3 times.

• Hash set: encounter 2 at index 0. See 2 again at index 3 → return 2.
• Pigeonhole: check arr[0]==arr[1] (2==1? no), arr[0]==arr[2] (2==3? no), arr[1]==arr[2] (1==3? no), arr[2]==arr[3] (3==2? no), arr[3]==arr[4] (2==2? yes) → return 2.

Common mistakes candidates make

• Sorting the array first (O(n log n) when O(n) is achievable).
• Not recognizing the pigeonhole approach for O(1) space.
• Iterating only adjacent pairs (missing the arr[i]==arr[i+2] check needed for pigeonhole).
• Returning the count instead of the element value.

Interview preparation tip

When an element appears N times in an array of size 2N, it must appear in at least one of every two consecutive pairs — use the pigeonhole principle. This O(1) space observation is impressive in interviews. Practice recognizing when high-frequency guarantees allow O(1) space solutions instead of hash maps. These density-based observations are common in array frequency problems.