N-Repeated Element in Size 2N Array

Posted on

Problem

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; }
        set.add(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.

Solution

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)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 dd, the array would be at least d(N1)+1d(N1)+1 long. Since we know that it is 2N2N long, we can conclude that d2N1N1d2N1N1, 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.

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.

Leave a Reply

Your email address will not be published. Required fields are marked *