You are given an integer array nums with the following properties:
nums.length == 2 * n.nums contains n + 1 unique elements.nums is repeated n times.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] <= 104nums contains n + 1 unique elements and one of them is repeated exactly n times.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.
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.
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.
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.
Time Complexity: O(N log N), due to the sorting process.
Space Complexity: O(1) in place sorting.
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.
Python
Java
C++
Go
TypeScript
JavaScript
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).
Python
Java
C++
Go
TypeScript
JavaScript
| 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 | — |
| 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 |
N-Repeated Element in Size 2N Array | Multiple Ways | Detailed For Beginners | Leetcode 961 | MIK • codestorywithMIK • 4,425 views views
Watch 9 more video solutions →Practice N-Repeated Element in Size 2N Array with our built-in code editor and test cases.
Practice on FleetCode