Howdy!
This is day 19 of my coding diary and I am pretty excited to share today's challenge with you guys!
Spoiler Alert  This is one of the interesting problems I have ever encountered. I feel every easy problem has a really smart hidden approach.
Problem of the day  NRepeated Element in Size 2N Array
Tag  Easy
You are given an integer array nums
with the following properties:

nums.length == 2 * n
. 
nums
containsn + 1
unique elements.  Exactly one element of
nums
is repeatedn
times.
Return the element that is repeated n
times.
Example 1:
Input: nums = [1,2,3,3]
Output: 3
Ahh, very basic problem. Just use a hashmap, store the count and return a result that has more than one reputation.
But wait, I could smell the trap here. Leetcode didn't seem happy with my old school hashmap approach (O(n) time and O(n) space)
.
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
map<int,int> list;
for(int num: nums) {
list[num]++;
}
for(auto val: list) {
if(val.second == nums.size()/2) return val.first;
}
return 1;
}
};
Is it even possible to optimize it further?
Let's find out!
So, if we observe more closely, we can see that, if a number is repeated n times, in an array of length 2 * n
, the repeated number will have to appear either next to each other (nums[i] and nums[i+1]
) or after another (nums[i] and nums[i+2]
).
I know it was tough, read it again. It took even, me some time to digest.
I was literally, blown away with the intuition. It comes with practice and solving problems of different  different patterns.
The edge case is [1,2,3,1]. In this case, we just return the last element.
Here is the code
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[nums.size()1];
}
};
This solution has the O(n)
runtime.
Learning
 Never settle for the first approach getting accepted, check out how others have done it. It's a great learning experience.
Thanks for being part of my dailycodeworkout journey. As always, if you have any thoughts about anything shared above, don't hesitate to reach out.
You might like previous editions of my coding diary
 Day #18  Count Negative Numbers in a Sorted Matrix.
 Day #17  Sum of Unique Elements.
 Day #16  Best Time to Buy and Sell Stock.
 Day #15  Count Number of Pairs With Absolute Difference K.
 Day #14  Minimum Number of Operations to Move All Balls to Each Box.
 Day #13  Number Of Rectangles That Can Form The Largest Square.
Top comments (0)