N-Repeated Element in Size 2N Array

The task is taken from leetcode

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

Example 1:

Input: [1,2,3,3] Output: 3

Example 2:

Input: [2,1,2,5,3,2] Output: 2

Example 3:

Input: [5,1,5,2,5,3,5,4] Output: 5

Note:

4 <= A.length <= 10000 0 <= A[i] < 10000 A.length is even

My solution

var repeatedNTimes = function(A) {
const set = new Set();
for (const n of A) {
if (set.has(n)) { return n; }
}
};


I didn't do much with the information size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times. I think these information is not needed to solve the problem efficiently. I also wonder whether there is a bitwise or purely math based solution to the task.

• Your solution is optimal.All that could be improved is the hashing of each item, In JS you can not write low level and thus improve the hashing (with exception of webAsm (if you consider it JS) but that is still very immature and would only give advantage for very large data sets) Apr 22, 2019 at 15:02

In the worst case (the repeated element occupies the second half of the array), the set will accommodate all N non-repeated elements, therefore the space complexity of the solution is $$\O(N)\$$.

Your intuition is correct; the solution doesn't use the important information. It is used to find out how far apart the repeated elements are. If a distance between them is at least $$\d\$$, the array would be at least $$\d\cdot(N-1) + 1\$$ long. Since we know that it is $$\2N\$$ long, we can conclude that $$\d \le \dfrac{2N-1}{N-1}\$$, which is effectively 2 for N > 2. It is enough to compare each a[i] with a[i+1] and a[i+2]. The space complexity is now constant.

• Beware that there is one exception to this, when the length of an array is 4, and both repeating elements are on the edges like this: [3, 1, 2, 3], then the distance is 3. In all other cases (array length even & 6+), the maximum distance is indeed 2. So it makes sense to check for if len(arr) == 4 && arr[0] == arr[3] { return arr[0] } first before the for loop, and only then proceed in checking for arr[i] == arr[i+1] || arr[i] == arr[i+2] Nov 3, 2020 at 19:19

I see in revision 3 that the else keyword and block was replaced by the single line that was in the block. That is a good simplification. Some developers aim to avoid the else keyword with techniques like returning early (like this code) and other similar techniques.

The function declaration uses the var keyword. Unless the scope needs to be broader or it needs to be re-assigned, const could have been used.

The suggestion in vnp's answer to check each element with the following two is a good one to reduce the space complexity. Another technique to do so would be to utilize Array.prototype.indexOf() passing the current index + 1 as the second argument (i.e. fromIndex). If that returns a value greater than -1 (or even the current index) then you would know the value is repeated. However this may be sub-optimal because it would require an extra function call.

Beware: the above answers and comments are not optimal! (although VNP above provides a good mathematical explanation of the following)

Using the Boyer-Moore Voting algorithm, a solution can be determined in O(n) time but also O(1) space. Any repeated digit will be the answer. Therefore, spreading out the N digits of the repeated value results in two cases:

1. The two values are side-by-side: in that case check every tuple for equality (when A[i] == A[i + 1] your answer is at A[i]).
2. The repeated digit is spread out evenly (this occurs at most every second value, therefore, if the above fails, check A[i] == A[i + 2]).

This algorithm is a rough explanation, but crucially eliminates the need for a set. There is one edge case when the length of the values is four and the majority item is spread out on the edges.

• That seems to be the same as vnp's suggested improvement. What's different, other than your observation that it can fail with N==2? Jun 13, 2021 at 20:06
• Whoops, didn't see their submission. Just adding some extra information about efficiency and more intuition. Jun 16, 2021 at 2:02
• Not sure which answers you mean by "above", as that set changes according to how each reader sorts the answers. Jun 18, 2021 at 8:53