N-Repeated Element in Size 2N Array.

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 contains n + 1 unique elements.
Exactly one element of nums is repeated n 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