Challenge #19 - N-Repeated Element in Size 2N Array.
Tags: programming, computerscience, codenewbie, beginners
Published: 2021-10-07 06:19:47

Howdy!

This is day 19 of [my coding diary](https://www.pankajtanwar.in/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. 

<hr/>

**Problem of the day** - [N-Repeated Element in Size 2N Array](https://leetcode.com/problems/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

<hr/>

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)`.    

```cpp
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!

<hr/>

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**

```cpp
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](https://twitter.com/the2ndfloorguy).

<hr/>

You might like previous editions of [my coding diary](/coding-diary)

- [Day #18 - Count Negative Numbers in a Sorted Matrix.](https://www.pankajtanwar.in/code/count-negative-numbers-in-a-sorted-matrix/)
- [Day #17 - Sum of Unique Elements.](https://www.pankajtanwar.in/code/sum-of-unique-elements/)
- [Day #16 - Best Time to Buy and Sell Stock.](https://www.pankajtanwar.in/code/best-time-to-buy-and-sell-stock/)
- [Day #15 - Count Number of Pairs With Absolute Difference K.](https://www.pankajtanwar.in/code/count-number-of-pairs-with-absolute-difference-k/)
- [Day #14 - Minimum Number of Operations to Move All Balls to Each Box.](https://www.pankajtanwar.in/code/minimum-number-of-operations-to-move-all-balls-to-each-box/)
- [Day #13 - Number Of Rectangles That Can Form The Largest Square.](https://www.pankajtanwar.in/code/number-of-rectangles-that-can-form-the-largest-square/)