N-Repeated Element in Size 2N Array
Find the value that appears N times in a 2N array — hash set or adjacent-pair scan.
2 min read
hash-set arrays
Problem#
In an array of length 2N containing N + 1 unique values, exactly one value appears N times. Find it.
Examples#
[1,2,3,3]→3.[2,1,2,5,3,2]→2.[5,1,5,2,5,3,5,4]→5.
Constraints#
4 <= nums.length <= 10^4, even length.
Hints#
Hint
If a value repeats, two copies must be within 3 positions of each other — check every adjacent pair, then the gap-2 pair as fallback.
Approach#
The simplest correct answer is a hash set: return the first repeat. The constant-space version: any value repeating N times in 2N slots must have two copies within distance 3, so check nums[i] == nums[i+1] || nums[i] == nums[i+2] || nums[i] == nums[i+3] for some i.
Solution#
class Solution {public: int repeatedNTimes(vector<int>& nums) { unordered_set<int> seen; for (int v : nums) { if (!seen.insert(v).second) return v; } return -1; // unreachable per constraints }};func repeatedNTimes(nums []int) int { seen := map[int]bool{} for _, v := range nums { if seen[v] { return v } seen[v] = true } return -1}from typing import List
class Solution: def repeatedNTimes(self, nums: List[int]) -> int: seen: set[int] = set() for v in nums: if v in seen: return v seen.add(v) return -1function repeatedNTimes(nums) { const seen = new Set(); for (const v of nums) { if (seen.has(v)) return v; seen.add(v); } return -1;}class Solution { public int repeatedNTimes(int[] nums) { Set<Integer> seen = new HashSet<>(); for (int v : nums) { if (!seen.add(v)) return v; } return -1; }}function repeatedNTimes(nums: number[]): number { const seen = new Set<number>(); for (const v of nums) { if (seen.has(v)) return v; seen.add(v); } return -1;}Editorial#
Hash-set returns the first duplicate found, which is necessarily the N-repeated value (other values appear once). The constant-space variant exploits the pigeonhole bound — N copies in 2N slots forces two copies within distance 3.
Complexity#
- Time: O(N).
- Space: O(N) for the set; O(1) for the pigeonhole variant.
Concept revision#
Related#