2
\$\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\$
  • \$\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 at 15:02
3
\$\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
\$\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, const could have been used unless it needs to be re-assigned.


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.indedOf() 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\$

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.