firstDuplicate question on CodeSignal in Javascript

user_17591453 0
Viewed 809

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.

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.

testcase algorithm javascript
1 Answers

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.

user_95152070
Related