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 - N-Repeated 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 daily-code-workout 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)