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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N log N), due to the sorting process.
Space Complexity: O(1) in place sorting.
| 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. |
Leetcode: N-Repeated Element in Size 2N Array || Java programming language|| arrays • TKGgames • 2,009 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