N-Repeated Element in Size 2N Array — Problem & Solution
N-Repeated Element in Size 2N Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
N-Repeated Element in Size 2N Array is an easy coding problem on arrays and hash table, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of length 2n containing n + 1 distinct values, exactly one of which appears n times.
Return that repeated value.
Example 1
Input: nums = [1,2,3,3]
Output: 3
Example 2
Input: nums = [2,1,2,5,3,2]
Output: 2
Example 3
Input: nums = [5,1,5,2,5,3,5,4]
Output: 5
Constraints
nums.length is even and at least 40 <= nums[i] <= 10000nums contains n + 1 distinct values, one repeated n times.
Hints for N-Repeated Element in Size 2N Array
Hint 1
Every other value appears exactly once, so the first value you see twice is the answer.
Hint 2
A set is enough — no counting needed.
Hint 3
The structure also guarantees two copies appear within any window of four, if you want O(1) space.
How to solve N-Repeated Element in Size 2N Array
All other values are unique, so the very first repeat encountered while scanning must be the target.
Approach
- Keep a set of values seen so far.
- For each element, return it immediately if it is already in the set.
- Otherwise add it and continue.
Why it works
Only one value repeats at all, so any collision identifies it. The guarantee that it appears n times means a collision is certain before the array ends.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Counting frequencies and taking the maximum also works but does more work than needed.
- The 'majority element' voting algorithm is not valid here — the repeated value occupies exactly half the array, not more.
Reference solution
Python
from typing import List
def repeatedNTimes(nums: List[int]) -> int:
seen = set()
for x in nums:
if x in seen:
return x
seen.add(x)
return -1Java
public static int repeatedNTimes(int[] nums) {
HashSet<Integer> seen = new HashSet<>();
for (int x : nums) {
if (!seen.add(x)) return x;
}
return -1;
}C++
int repeatedNTimes(vector<int>& nums) {
unordered_set<int> seen;
for (int x : nums) {
if (seen.count(x)) return x;
seen.insert(x);
}
return -1;
}JavaScript
var repeatedNTimes = function(nums) {
const seen = {};
for (let i = 0; i < nums.length; i++) {
const k = String(nums[i]);
if (seen[k] === true) return nums[i];
seen[k] = true;
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets