- Published on

# N-Repeated Element in Size 2N Array.

- Authors
- Name
- Pankaj Tanwar
- @the2ndfloorguy

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

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