N-Repeated Element in Size 2N Array
EasyPrompt
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: 3Example 2:
Input: nums = [2,1,2,5,3,2]
Output: 2Example 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.
Approaches
4 approaches with complexity analysis and trade-offs.
This approach uses two nested loops to compare every element of the array with every other element. When a pair of identical elements is found, that element is the answer. This is the most straightforward but least efficient method.
Algorithm
- Use a nested loop structure.
- The outer loop iterates from the first element to the last, with index
i. - The inner loop iterates from
i + 1to the last element, with indexj. - Inside the inner loop, compare
nums[i]andnums[j]. - If they are equal,
nums[i]is the repeated element, so return it. - Since it's guaranteed that exactly one element is repeated
ntimes, this loop will always find the repeated element.
Walkthrough
The brute-force solution involves a nested iteration over the array. The outer loop selects an element, and the inner loop scans the rest of the array to find a duplicate. Because the problem guarantees that exactly one element is repeated, the first duplicate we find must be the N-repeated element.
class Solution { public int repeatedNTimes(int[] nums) { int N = nums.length; for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) { if (nums[i] == nums[j]) { return nums[i]; } } } return -1; // Should not be reached given the problem constraints }}Complexity
Time
O(N^2) - Where N is the length of the `nums` array. For each element, we iterate through the rest of the array, leading to a quadratic number of comparisons.
Space
O(1) - No extra data structures are used, so the space complexity is constant.
Trade-offs
Pros
Simple to understand and implement.
Uses constant extra space, O(1).
Cons
Highly inefficient with a time complexity of O(N^2).
It will be very slow for large input arrays and may result in a 'Time Limit Exceeded' error on online judges.
This method involves sorting the array first. Once sorted, the n identical elements will be grouped together. A single pass over the sorted array can then easily find an element that is the same as its neighbor.
Algorithm
- Sort the input array
numsin non-decreasing order. - After sorting, all
ncopies of the repeated element will be adjacent to each other. - Iterate through the sorted array from the first element up to the second-to-last element.
- Compare each element
nums[i]with the next elementnums[i+1]. - If
nums[i] == nums[i+1], you have found the repeated element. Returnnums[i].
Walkthrough
By sorting the array, we ensure that all equal elements are placed next to each other. Since one element is repeated n times, there must be at least one pair of adjacent elements that are identical. We can then iterate through the array and check for this condition.
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; // Should not be reached }}Complexity
Time
O(N log N) - Where N is the length of the array. This is dominated by the time taken to sort the array.
Space
O(log N) to O(N) - The space complexity depends on the sorting algorithm used. In Java, `Arrays.sort()` for primitives uses a variant of Quicksort which requires O(log N) space for the recursion stack on average. Mergesort would require O(N) space.
Trade-offs
Pros
Conceptually simple and easy to implement.
More efficient than the brute-force approach.
Cons
The time complexity is dominated by the sorting algorithm, which is generally O(N log N).
It either modifies the original array or requires O(N) space to store a copy.
The space complexity for sorting can be up to O(N) depending on the implementation.
A more efficient approach is to use a hash set to keep track of the elements we have seen. We iterate through the array, and for each element, we check if it's already in the set. If it is, we've found our repeated element. If not, we add it to the set and continue.
Algorithm
- Initialize an empty
HashSetto store unique elements encountered so far. - Iterate through each number
numin the input arraynums. - For each
num, check if it is already present in theHashSet. - If it is, then
numis the repeated element. Returnnum. - If it is not, add
numto theHashSetand continue to the next element.
Walkthrough
This approach leverages the O(1) average time complexity of hash set operations. We iterate through the array once. For each element, we try to add it to a set of seen numbers. If the element is already in the set, the add operation fails (or a contains check returns true), and we know we have found the duplicate. Since only one number is duplicated, this must be the answer.
import java.util.HashSet;import java.util.Set; class Solution { public int repeatedNTimes(int[] nums) { Set<Integer> seen = new HashSet<>(); for (int num : nums) { if (!seen.add(num)) { return num; } } return -1; // Should not be reached }}Complexity
Time
O(N) - Where N is the length of the array. We iterate through the array once, and hash set operations (add, contains) take O(1) time on average.
Space
O(n) - In the worst-case scenario, we might have to store all `n` unique elements plus one instance of the repeated element before finding the duplicate. The size of the hash set is proportional to `n`.
Trade-offs
Pros
Achieves linear time complexity, O(N), which is very efficient.
Simple to implement.
Cons
Requires extra space to store the seen elements, which can be up to O(n) in the worst case.
This optimal approach is based on a mathematical insight derived from the problem's constraints. Given that half the elements in a 2n size array are a single repeated number, it's guaranteed that two of these repeated numbers must lie very close to each other. Specifically, the distance between two identical items will be at most 3. This allows us to find the repeated element in a single pass with constant extra space.
Algorithm
- The core idea is that the repeated element must have at least two of its copies close to each other.
- It can be proven that for an array with the given properties, there must be two identical elements with a distance of 1, 2, or 3.
- Iterate through the array from left to right, starting from index 1.
- For each element
nums[i], compare it with its immediate neighbors atnums[i-1],nums[i-2], andnums[i-3](if they exist). - If a match is found, return that element.
Walkthrough
Let the repeated element be x. There are n copies of x and n other unique elements in an array of size 2n. Let's assume for contradiction that any two copies of x are separated by a distance of at least 4 (i.e., there are at least 3 other elements between them). To place n copies of x this far apart, the total length of the array would need to be at least 1 (for the first x) + (n-1) * 4 = 4n - 3. However, the array length is 2n. The inequality 2n >= 4n - 3 simplifies to 3 >= 2n, which is false for any n >= 2 (as per the problem constraints). This contradiction proves that our assumption was wrong. Therefore, there must be at least one pair of x's with a distance of 1, 2, or 3. We can find this pair by checking each element against its three predecessors.
class Solution { public int repeatedNTimes(int[] nums) { for (int i = 2; i < nums.length; i++) { // Check for distance 1 or 2 if (nums[i] == nums[i-1] || nums[i] == nums[i-2]) { return nums[i]; } } // The only remaining case not covered by the loop is a pattern like [x, y, z, x] // which only happens for n=2. In this case, nums[0] is the answer. return nums[0]; }}A slightly more general implementation covering all distances up to 3:
class Solution { public int repeatedNTimes(int[] nums) { for (int k = 1; k <= 3; ++k) { for (int i = 0; i < nums.length - k; ++i) { if (nums[i] == nums[i+k]) { return nums[i]; } } } return -1; // Should not be reached }}Complexity
Time
O(N) - We perform a single pass through the array (or a fixed number of passes, 3, which is still O(N)). For each element, we do a constant number of comparisons.
Space
O(1) - This approach uses only a few variables for loops and indices, requiring constant extra space.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1).
Cons
The underlying mathematical proof is not immediately obvious.
Solutions
Solution
/** * @param {number[]} nums * @return {number} */ var repeatedNTimes = function ( nums ) { const s = new Set (); for ( const x of nums ) { if ( s . has ( x )) { return x ; } s . add ( x ); } };class Solution {public int repeatedNTimes(int[] nums) { Set<Integer> s = new HashSet<>(nums.length / 2 + 1); for (int i = 0;; ++i) { if (!s.add(nums[i])) { return nums[i]; } } }}class Solution {public: int repeatedNTimes(vector<int> &nums) { unordered_set<int> s; for (int i = 0;; ++i) { if (s.count(nums[i])) { return nums[i]; } s.insert(nums[i]); } }};class Solution: def repeatedNTimes(self, nums: List[int]) -> int: s = set() for x in nums: if x in s: return x s . add(x)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.