Searching for first duplicate element in huge array of numbers

Question

Trying to solve this question - 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.

Here's my solution -

function firstDuplicate(a) {
  for (let i = 0; i < a.length; i++) {
    if (a.indexOf(a[i]) !== i) {
      return a[i];
    }
  }

  return -1;
}

Problem - one of the acceptance criteria is, algorithm should find the first duplicate value in under 4 seconds, which I am not able to achieve when input array is huge. I tested with input array that has 100k items in it and my algorithm took 5+ seconds. Can someone help me tweak my code so it would finish in under 4 seconds?

Thanks a lot!

Answer 1

You've to walk through that array and collect elements to temporary object that keeps number (element) as key and some boolean value as index.

On every iteration check that temporary object has that key.

const bigArray = [];


for(let i = 0; i<1000000; i++) {
  bigArray.push(i);
}


for(let i = 0; i<1000000; i++) {
  bigArray.push(parseInt(Math.random()*1000000));
}


const firstDuplicateInArray = array => {
  const temp = {};
  for (let i = 0; i < array.length; i++) {
    if (temp[array[i]] === true) {
      return array[i];
    }
    temp[array[i]] = true;
  }
  return -1;
};

const start = new Date().getTime();
console.log('Time start:', start);

console.log('Found 1st duplicate:', firstDuplicateInArray(bigArray));

const end = new Date().getTime();
console.log('Time end:', end);

console.log('Time taken:', end - start, 'microseconds');

P.S. Set more than 2 times slower (depending on size of array):

const bigArray = [];


for(let i = 0; i<1000000; i++) {
  bigArray.push(i);
}


for(let i = 0; i<1000000; i++) {
  bigArray.push(parseInt(Math.random()*1000000));
}


function firstDuplicate(a) {
  const r = new Set();
  for (let e of a) {
    if (r.has(e)) return e;
    else r.add(e);
  }
  return -1;
}

const start = new Date().getTime();
console.log('Time start:', start);

console.log('Found 1st duplicate:', firstDuplicate(bigArray));

const end = new Date().getTime();
console.log('Time end:', end);

console.log('Time taken:', end - start, 'microseconds');