Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

firstDuplicate question on CodeSignal in Javascript

I couldn’t figure out why I passed 22/23 on this challenge and not able to solve the last test case since it was hidden.. The feedback from the CodeSignal is

Tests passed: 22/23. Execution time limit exceeded: Program exceeded
the execution time limit. Make sure that it completes execution in a
few seconds for any possible input.

Challenge
Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

Example

For a = [2, 1, 3, 5, 3, 2], the output should be solution(a) = 3.

There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than the second occurrence of 2 does, so the answer is 3.

For a = [2, 2], the output should be solution(a) = 2;
For a = [2, 4, 3, 5, 1], the output should be solution(a) = -1.

Input/Output

[execution time limit] 4 seconds (js)

[input] array.integer a

Guaranteed constraints:
1 ≤ a.length ≤ 105,
1 ≤ a[i] ≤ a.length.

[output] integer

The element in a that occurs in the array more than once and has the minimal index for its second occurrence. If there are no such elements, return -1.

My code

function solution(a) {
  let first = Infinity
  for ( let i = 0; i<a.length; i++ ) {
      let pointer = i+1;
      while (pointer <a.length) {
          if (a[i] === a[pointer] && pointer<first) {
              first = pointer;
          } 
          pointer +=1
      }
  } 
  if (first === Infinity) {
      return -1
  }
  return a[first]
}

Thank you.

>Solution :

In bad cases, you’re iterating over the whole array for every element in it – O(n ^ 2). The inner while(pointer < a.length) results in the argument taking too much time.

Instead, make a Set of elements found so far, and return when the first duplicate element is found (which will be the minimal second index).

const solution = (a) => {
  const set = new Set();
  for (const item of arr) {
    if (set.has(item)) return item;
    set.add(item);
  }
  return -1;
};

Since this has no nested loop (.has and .add is O(1)), this is O(n) overall, which should be quick enough.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading