4
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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) \$\endgroup\$ – Blindman67 Apr 22 '19 at 15:02
5
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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] \$\endgroup\$ – IvanD Nov 3 '20 at 19:19
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

New contributor
John McCambridge is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
2
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ – Toby Speight Jun 13 at 20:06
  • \$\begingroup\$ Whoops, didn't see their submission. Just adding some extra information about efficiency and more intuition. \$\endgroup\$ – John McCambridge yesterday
-1
\$\begingroup\$

The code of the author of this topic not so easy to understand for me. I think this approach more readable and laconic

const repeatedNTimes = (A) => A.find((num, i, arr) => arr.slice(i + 1).includes(num));
New contributor
HackerMF is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
6
  • 1
    \$\begingroup\$ You did not review the code \$\endgroup\$ – Billal Begueradj yesterday
  • \$\begingroup\$ I guess everthin' is all clear what I wrote. I don't know what to write yet \$\endgroup\$ – HackerMF yesterday
  • \$\begingroup\$ You suggested an alternative approach without reviewing the existing code \$\endgroup\$ – Billal Begueradj yesterday
  • \$\begingroup\$ Greetings, this answer neither reviews the code, nor produces a correct result. \$\endgroup\$ – rolfl yesterday
  • \$\begingroup\$ @rolfl I was hasty to send the code, thnx, fix it)) \$\endgroup\$ – HackerMF yesterday

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.