Code Logo

N-Repeated Element in Size 2N

Published at23 Jul 2026
Created by
Easy 0 views
Like0

You are given an integer array of size 2N. There are N+1 unique elements in the array, and one of them is repeated exactly N times. All other elements appear exactly once. Find the element that is repeated N times.

A hash set provides the simplest solution: iterate through the array. If an element is already in the set, it is the repeated element (the first duplicate found). This works because the repeated element appears N times, and the first time we encounter it the second time, we know it's the answer.

For example, nums = [1,2,3,3] has N=2. Elements 1 and 2 appear once. Element 3 appears twice (N times). The answer is 3.

This problem tests understanding of hash sets and the ability to recognize that the first duplicate found is guaranteed to be the answer because the N-repeated element appears N times while all others appear exactly once.

The hash set solution works because the N-repeated element appears N times, making it the first element that is encountered a second time. All other elements appear exactly once, so they are added to the set and never seen again. This simple observation makes the problem trivial with a hash set.

The array size is always 2N, with N unique elements plus one element repeated N times. This guarantees that the repeated element will be found before the end of the array.

Example Input & Output

Example 1
Input
[1,2,3,3]
Output
3
Explanation

3 is repeated N=2 times.

Example 2
Input
[5,1,5,2,5,3,5,4]
Output
5
Explanation

5 appears 4 times (N=4).

Example 3
Input
[2,1,2,5,3,2]
Output
2
Explanation

2 appears 3 times (N=3).

Algorithm Flow

Recommendation Algorithm Flow for N-Repeated Element in Size 2N
Recommendation Algorithm Flow for N-Repeated Element in Size 2N

Solution Approach

Use a hash set. For each element, if already in set, return it. Otherwise, add to set.

function solution(nums) {
  var seen = {};
  for (var i = 0; i < nums.length; i++) {
    if (seen[nums[i]]) return nums[i];
    seen[nums[i]] = true;
  }
  return -1;
}

Time O(n), Space O(n).

Best Answers

java
import java.util.*;
class Solution {
    public int solution(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int n : nums) { if (!seen.add(n)) return n; }
        return -1;
    }
}