Written by Blaise M on Jan 3rd, 2026
Difficulty: Easy
Categories: Array, Hash Table , Sliding Window, Math
Language(s): C++
Complexity:
- Solution 1 (Set) : O(N) time , O(N) space
- Solution 2 (Boyer Moore): O(N) time , O(1) space
- Solution 2 (Pidgeon Hole + Sliding Window): O(N) time, O(1) space
Solution Video
Coming Soon! :)
Problem Summary
This problem is essentially a Majority Element problem with stricter constraints.
We are tasked with identifying a target element given three main constraints:
- Input Array Length = 2 * N : This
Nvalue will be important to following rules - Target occurs N Times: Since our target occurs
Ntimes , and the array is of length2N, we can deduce our target always takes up exactly half of the input array - Input Array has N+1 Unique Elements: Given our target value takes up
Nindicies, this rule tells us that all other values in the input array will occur exactly once.
Edge Cases, Hints, and Things to Consider
- Are there any patterns target values will adhere to in the input array given the constraints? such as the fact they account for half the array, or that only the target can occur more than once?
Approach 1 : HashMap/Set
Intuition / High-Level Approach
Since we know that only the target value can occur more than once, we can map the values we see as we traverse the input array , return once we see a value we have already seen.
Note: I used a set for simplicity , since we only need to see twice to verify
Solution
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
unordered_set<int> seen ;
for(auto num : nums){
if(seen.count(num) > 0) return num;
else seen.insert(num);
}
return -1;
}
};
Approach 2: Boyer Moore Algorithm
Intuition / High-Level Approach
I knew there was a way to solve this problem in constant memory without a map or set, but I wasn't entirely sure how to do so. I did some reading in the discussion board around Boyer Moore, but I wasn't particularly familiar with the algorithm.
After reading the GeeksForGeeks article (see resources section) and watching a couple youtube videos , my basic understanding is that Boyer Moore is an algorithm for finding the majority element of an array in linear time using two variables we will call candidate and count.
Essentially, at the start of our search we initialize candidate to be the first value in the array , and count to be 1 to represent the seen value at index 0.
Now , as we iterate over the remaining values , we can manipulate the variables as follows:
IF the current value is equal to the candidate value, we increment the count IF the current value is not equal to the candidate value, we decrement the count. If doing so results in count being equal to 0 , then the current value becomes our new candidate, and we reset the count to 1.
The basic intuition here is that when we finish iterating over the array , whatever the candidate is set to must be the majority element , because that is the only way the count could have survived being zeroed.
However, Boyer–Moore only guarantees correctness when an element appears more than half the time. In this problem, the repeated element appears exactly half the time, so the standard majority guarantee no longer applies.
Because of this, certain arrangements, such as the target value alternating perfectly with unique values can cause the count to repeatedly drop to zero and reset, making the final candidate ambiguous without additional checks. To account for this, we can add a small base-case to check for this alternating pattern before we start iteration.
Solution
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
int candidate = nums[0] ;
int count = 1;
// catch the edge case by checking for a [target,x,target] pattern
if(nums.front() == nums[2]) return nums.front();
for(int i = 1 ; i < nums.size() ; i++){
if(candidate == nums[i]) count++;
else if(--count == 0){
candidate = nums[i];
count = 1;
}
}
return candidate;
}
};
Approach 3: Pigeon Hole Principle
Intuition / High-Level Approach
I had a theory that the edge case I used for my Boyer Moore Algorithm might be the key to a sliding window style approach , but I wasn't quite sure how until I stumbled upon a cool solution by eunice, which makes use of the pigeon hole principle. Be sure to read their solution and give them an upvote, they go way more in depth on this one than I will here.
Essentially , Because the repeated value appears N times in 2N slots, some two occurrences must be within 2 indices of each other, such as :
[ target, non-target, target] or [target,target, non-target]
knowing this , if we set our window size to 3 , and slide across the array window by window, as soon as we find a window where the first value equals the second or the third, we have found our target and we can return.
We must only account for one edge case , shown in the following example.
[1,2,3,3]
As you can see, the target value is 3 , but it is occurs in the last two indicies. Because of this , our window search won't catch it. We will see:
iteration 1 : [1,2,3] -> 1 != 2, 1 != 3 -> no dup
iteration 2 : [2,3,3] -> 2 != 3, 2 != 3 -> no dup
and then our loop will break, skipping the last two indicies.
However, we know that 0 -> n-3 are not eligible targets per our iterative tests.
We also know tha n-2 is not the target , because it would've been caught already since it's been compared in the second and third position of it's two preceding values, respectively. It's only other eligible pair would be the last value in the array.
So, we can safely assume that when we get this far, the target value is the last value in the array , because that is the only value we haven't disqualified in our tests thus far.
Solution
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
for(int i = 0 ; i < nums.size()-2 ;i++){
if(nums[i] == nums[i+1] || nums[i] == nums[i+2]) return nums[i];
}
return nums.back();
}
};
Useful Resources
Please upvote if this helped you out, it motivates me to keep writing these :)