N-Repeated Element in Size 2N Array solution and explanation
Google
9 more videos on this problem
N-Repeated Element in Size 2N Array | Multiple Ways | Detailed For Beginners | Leetcode 961 | MIKcodestorywithMIK · 24:19 · 4K views
N-Repeated Element in Size 2N Array | LeetCode 961 | Optimized O(N) Space-Efficient SearchSanyam IIT Guwahati · 11:34 · 896 views
N-Repeated Element in Size 2N Array | LeetCode 961 | Theory + Python codeSai Anish Malla · 8:56 · 731 views
961. N-Repeated Element in Size 2N Array | Leetcode Daily - PythonLeetcode Daily · 7:49 · 639 views
N-Repeated Element in Size 2N Array - LeetCode #961algoviz-xyz · 2:17 · 624 views
Leetcode 961. N-Repeated Element in Size 2N ArrayAlgorithms Casts · 13:32 · 529 views
Daily Leetcode #2103: Jan 02, 2026 - 961. N-Repeated Element in Size 2N ArrayProgramming Live with Larry · 5:30 · 424 views
LeetCode 961 : N-Repeated Element in Size 2N Array | Solution in JAVAAmit Manjarly · 9:07 · 373 views
961. N-Repeated Element in Size 2N Array (Leetcode Easy)Programming Live with Larry · 9:18 · 263 views
LeetCode 961. N-Repeated Element in Size 2N Array Solution Explained - JavaAlgorithms and Data Structures Course · 4:33 · 239 views
The problem
You are given an integer array nums with the following properties:
nums.length == 2 * n.numscontainsn + 1unique elements.- Exactly one element of
numsis repeatedntimes.
Return the element that is repeated n times.
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:
2 <= n <= 5000nums.length == 2 * n0 <= nums[i] <= 104numscontainsn + 1unique elements and one of them is repeated exactlyntimes.
Approach overview
Problem Overview: You are given an array of size 2N that contains N+1 unique values. Exactly one element appears N times while every other element appears once. The task is to identify the element that repeats N times.
Approach 1: HashMap / Hash Set (O(n) time, O(n) space)
The most direct solution uses a hash-based structure to track elements you've already seen. Iterate through the array once and insert each value into a HashSet (or store frequency in a HashMap). If an element already exists in the set, you've found the repeated element and can return it immediately. Hash lookups run in constant time on average, so the entire scan completes in O(n) time with O(n) auxiliary space. This approach works for any ordering of elements and is typically the expected interview solution when using a hash table.
Approach 2: Sorting (O(n log n) time, O(1) extra space)
Another option is to sort the array first. After sorting, identical elements become adjacent. Scan the sorted array and check neighboring values; the repeated element will appear multiple times consecutively. Sorting takes O(n log n) time, and the scan afterward is O(n). If the sorting algorithm is in-place, the extra memory cost is O(1) (or O(log n) depending on implementation). This method relies on the properties of a sorted array and avoids using additional hash storage, though it is slower than the optimal approach.
Recommended for interviews: The hash set approach is the cleanest and fastest solution with O(n) time complexity. It demonstrates familiarity with constant-time lookups using a hash table. Sorting works but is less optimal, so it is usually discussed as an alternative when minimizing extra memory or when sorting is already part of the workflow.
Approach 1: HashMap Approach
This approach uses a hashmap (or dictionary) to store the count of each element in the array. By iterating through the array and updating the map, we can easily identify the element that repeats n times by checking the count value.
def repeatedNTimes(nums):
counts = {}
for num in nums:
counts[num] = counts.get(num, 0) + 1
if counts[num] > 1:
return num
print(repeatedNTimes([1, 2, 3, 3]))import java.util.HashMap;
class Solution {
public int repeatedNTimes(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
if (map.get(num) > 1)
return num;
}
return -1; // Unreachable because of the problem guarantee
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 3, 3};
System.out.println(solution.repeatedNTimes(nums));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int repeatedNTimes(vector<int>& nums) {
unordered_map<int, int> count;
for (int num : nums) {
if (++count[num] > 1) return num;
}
return -1; // should never reach here
}
int main() {
vector<int> nums = {1, 2, 3, 3};
cout << repeatedNTimes(nums) << endl;
}function repeatedNTimes(nums) {
const map = {};
for (const num of nums) {
if (map[num]) return num;
map[num] = true;
}
}
console.log(repeatedNTimes([1, 2, 3, 3]));#include <stdio.h>
#include <stdlib.h>
int repeatedNTimes(int *nums, int numsSize) {
int *hash = (int *)calloc(10001, sizeof(int));
for (int i = 0; i < numsSize; i++) {
hash[nums[i]]++;
if (hash[nums[i]] > 1) {
free(hash);
return nums[i];
}
}
free(hash);
return -1; // This will never be reached according to the problem constraints
}
int main() {
int nums[] = {1, 2, 3, 3};
int result = repeatedNTimes(nums, 4);
printf("%d\n", result);
}using System;
using System.Collections.Generic;
class Solution {
public int RepeatedNTimes(int[] nums) {
Dictionary<int, int> map = new Dictionary<int, int>();
foreach (int num in nums) {
if (map.ContainsKey(num)) map[num]++;
else map[num] = 1;
if (map[num] > 1) return num;
}
return -1;
}
static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.RepeatedNTimes(new int[] { 1, 2, 3, 3 }));
}
}The Python solution uses a dictionary to map each number to its occurrence count. The function returns immediately when a count greater than one is detected.
Time Complexity: O(N), iterating over all elements.
Space Complexity: O(N), for the dictionary maintaining counts.
Approach 2: Sorting Approach
In this method, we first sort the array. If an element is repeated n times and the rest are unique, the repeated element must be at the center of the sorted array, appearing consecutively. Checking the middle indexes should reveal the repeated element.
def repeatedNTimes(nums):
nums.sort()
for i in range(len(nums) - 1):
if nums[i] == nums[i + 1]:
return nums[i]
print(repeatedNTimes([1, 2, 3, 3]))import java.util.Arrays;
class Solution {
public int repeatedNTimes(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == nums[i + 1]) {
return nums[i];
}
}
return -1; // unreachable
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 3, 3};
System.out.println(solution.repeatedNTimes(nums));
}
}#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int repeatedNTimes(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 1; i++) {
if (nums[i] == nums[i + 1]) return nums[i];
}
return -1; // Unreachable
}
int main() {
vector<int> nums = {1, 2, 3, 3};
cout << repeatedNTimes(nums) << endl;
}function repeatedNTimes(nums) {
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] === nums[i + 1]) return nums[i];
}
}
console.log(repeatedNTimes([1, 2, 3, 3]));#include <stdio.h>
#include <stdlib.h>
int cmpfunc(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int repeatedNTimes(int *nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), cmpfunc);
for (int i = 0; i < numsSize - 1; i++) {
if (nums[i] == nums[i + 1]) {
return nums[i];
}
}
return -1; // Unreachable condition according to the problem
}
int main() {
int nums[] = {1, 2, 3, 3};
int result = repeatedNTimes(nums, 4);
printf("%d\n", result);
}using System;
class Solution {
public int RepeatedNTimes(int[] nums) {
Array.Sort(nums);
for (int i = 0; i < nums.Length - 1; i++) {
if (nums[i] == nums[i + 1]) return nums[i];
}
return -1; // unreachable
}
static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.RepeatedNTimes(new int[] { 1, 2, 3, 3 }));
}
}Python's solution leverages the built-in sort(), making it simple to identify the repeated number immediately after sorting.
Time Complexity: O(N log N), again due to the sort operation.
Space Complexity: O(1) for extra space.
Approach 3: Hash Table
Since the array nums has a total of 2n elements, with n + 1 distinct elements, and one element repeated n times, this means the remaining n elements in the array are all distinct.
Therefore, we only need to iterate through the array nums and use a hash table s to record the elements we've encountered. When we encounter an element x, if x already exists in the hash table s, it means x is the repeated element, and we can directly return x.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
function repeatedNTimes(nums: number[]): number {
const s: Set<number> = new Set();
for (const x of nums) {
if (s.has(x)) {
return x;
}
s.add(x);
}
}func repeatedNTimes(nums []int) int {
s := map[int]bool{}
for i := 0; ; i++ {
if s[nums[i]] {
return nums[i]
}
s[nums[i]] = true
}
}Approach 4: Mathematics
According to the problem description, half of the elements in the array nums are the same. If we view the array as a circular arrangement, then there is at most 1 other element between two identical elements.
Therefore, we iterate through the array nums starting from index 2. For each index i, we compare nums[i] with nums[i - 1] and nums[i - 2]. If they are equal, we return that value.
If we don't find the repeated element in the above process, then the repeated element must be nums[0], and we can directly return nums[0].
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function repeatedNTimes(nums: number[]): number {
for (let i = 2; i < nums.length; ++i) {
if (nums[i] === nums[i - 1] || nums[i] === nums[i - 2]) {
return nums[i];
}
}
return nums[0];
}func repeatedNTimes(nums []int) int {
for i := 2; i < len(nums); i++ {
if nums[i] == nums[i-1] || nums[i] == nums[i-2] {
return nums[i]
}
}
return nums[0]
}Complexity comparison
| Approach | Complexity |
|---|---|
| HashMap Approach | Time Complexity: O(N), iterating over all elements. |
| Sorting Approach | Time Complexity: O(N log N), again due to the sort operation. |
| Hash Table | – |
| Mathematics | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap / Hash Set | O(n) | O(n) | Best general solution with fast hash lookups |
| Sorting | O(n log n) | O(1) extra (depends on sort) | Useful when modifying the array is allowed and extra memory should be minimized |
Frequently asked questions
Is N-Repeated Element in Size 2N Array easy or hard?
This problem is classified as Easy. The main concept is recognizing duplicate detection using hashing or sorting, which are foundational techniques in array and hash table problems.
N-Repeated Element in Size 2N Array Python/Java solution
In Python, a set is typically used to track seen elements during a single pass through the array. In Java, a HashSet or HashMap provides the same functionality. Both implementations achieve O(n) time complexity with O(n) additional space.
How to solve N-Repeated Element in Size 2N Array in O(n)?
Use a HashSet while scanning the array. Insert each element as you iterate; if the element already exists in the set, return it immediately. Since hash lookups and insertions are O(1) on average, the entire algorithm runs in linear time.
What is the best approach for N-Repeated Element in Size 2N Array?
The hash set approach is the most efficient solution. Iterate through the array and store elements in a set. If an element already exists in the set, it is the repeated element. This method runs in O(n) time with O(n) space.
Is N-Repeated Element in Size 2N Array asked at Google/Amazon/Meta?
This problem is commonly used in technical interviews as a basic array and hash table exercise. Similar duplicate-detection patterns appear in interviews at companies like Amazon, Google, and Meta to test understanding of hashing and frequency counting.
What data structure is used in N-Repeated Element in Size 2N Array?
The most common data structure used is a hash set or hash map. It allows constant-time checks to determine whether an element has already appeared while scanning the array.
What is the time complexity of N-Repeated Element in Size 2N Array?
The optimal hash table solution runs in O(n) time because each element is processed once with constant-time hash lookups. A sorting-based approach requires O(n log n) time due to the sorting step.