N-Repeated Element in Size 2N Array - Solution & Explanation
Problem Statement
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.
The C solution uses an array hash of fixed size to act as a hashmap to count occurrences of each number. As soon as a number appears more than once, the function returns that number and frees the allocated memory.
Complexity
Time Complexity: O(N), where N is the length of the nums array because we iterate over it once.
Space Complexity: O(1), since the hashmap is of a fixed size of 10001.
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.
The C solution sorts the array with qsort, then checks adjacent elements for equality. The repeated element will be found in this check.
Complexity
Time Complexity: O(N log N), due to the sorting process.
Space Complexity: O(1) in place sorting.
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.
Code
Python
Java
C++
Go
TypeScript
JavaScript
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).
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| HashMap Approach | Time Complexity: O(N), where N is the length of the nums array because we iterate over it once. |
| Sorting Approach | Time Complexity: O(N log N), due to the sorting process. |
| Hash Table | — |
| Mathematics | — |
Detailed 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 |
Video Solution
N-Repeated Element in Size 2N Array | Multiple Ways | Detailed For Beginners | Leetcode 961 | MIK • codestorywithMIK • 4,525 views views
Watch 9 more video solutions →Frequently Asked Questions
Is N-Repeated Element in Size 2N Array easy or hard?
N-Repeated Element in Size 2N Array Python/Java solution
How to solve N-Repeated Element in Size 2N Array in O(n)?
What is the best approach for N-Repeated Element in Size 2N Array?
Is N-Repeated Element in Size 2N Array asked at Google/Amazon/Meta?
What data structure is used in N-Repeated Element in Size 2N Array?
What is the time complexity of N-Repeated Element in Size 2N Array?
Ready to solve this problem?
Practice N-Repeated Element in Size 2N Array with our built-in code editor and test cases.
Practice on FleetCode