N-Repeated Element in Size 2N Array

easy array hash set

Problem

You are given an integer array nums with a length of 2n where exactly one element is repeated n times and the remaining n elements are all distinct. Return the element that is repeated n times.

Inputnums = [1, 2, 3, 3]

Output3

The array has length 4 (n = 2). The value 3 appears n = 2 times; every other value appears once.

nums (comma-separated)

def repeated_n_times(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return x
        seen.add(x)
    return -1

function repeatedNTimes(nums) {
  const seen = new Set();
  for (const x of nums) {
    if (seen.has(x)) return x;
    seen.add(x);
  }
  return -1;
}

class Solution {
    public int repeatedNTimes(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) {
            if (seen.contains(x)) return x;
            seen.add(x);
        }
        return -1;
    }
}

int repeatedNTimes(vector<int>& nums) {
    unordered_set<int> seen;
    for (int x : nums) {
        if (seen.count(x)) return x;
        seen.insert(x);
    }
    return -1;
}

Explanation

The array has size 2n where one value appears n times and the other n values appear once each. The key insight: the repeated value is the only one that can appear twice, so the first time we see any duplicate, that is our answer.

We walk left to right keeping a hash set of values we have already seen. For each x, if it is already in the set we return it immediately; otherwise we add it and continue.

This works because every distinct value shows up once, while the special value shows up many times — so the earliest repeat must be that special value.

Example: nums = [1, 2, 3, 3]. We add 1, then 2, then 3. When we reach the second 3, it is already in the set, so we return 3.

Since set lookups are constant time, we find the answer in one quick pass without checking all pairs.

Time: O(n) Space: O(n)