Decrease execution time of "firstDuplicate" algorithm

Question

function firstDuplicate(a) {
  var numbers = {},
      res;

foo:
  for (var i = 0; i < a.length; i++) {
    for (var j = i + 1; j < a.length; j++) {
      if (a[i] === a[j]) {
        numbers[a[i]] = j - i;
        if (j - i === 1 ) {
            break foo;
        }
      }
    }
  }

  var keys = Object.keys(numbers),
      res = keys[0];

  keys.forEach(function (v) {
    res = numbers[res] > numbers[v] ? v : res;
  });

  console.log(res);

  return res === undefined ? -1 : Number(res);
}

This function returns the first duplicate value in the array of numbers.

I want to decrease its execution time. What changes should I do?

Examples

For a = [2, 3, 3, 1, 5, 2], the output should be firstDuplicate(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, 4, 3, 5, 1], the output should be firstDuplicate(a) = -1.

This functions definitely doesn't return "the first duplicate in the array". What do you really want to do? — Jakub Dąbek
– Jakub Dąbek, Commented Dec 24, 2017 at 12:27
@JakubDąbek I think he wants to return index of the first duplicate — vibhor1997a
– vibhor1997a, Commented Dec 24, 2017 at 12:30
I think OP wants an index where the next duplicate comes as soon as possible. But I think it fails, because numbers[a[i]] gets overridden so that it only looks at the last pair of duplicates for each value of a[i]. So if a = ['a', 'a', 'b', 'a'], then it will find the (1,3) pair instead of the (0,1) pair. But yes, this definitely needs more clarity. — David Knipe
– David Knipe, Commented Dec 24, 2017 at 12:39
@GaneshSundaram you want "the first duplicate value in the array of numbers". So if a = [4, 4, 9, 9] you want to return 4. What if a = [4, 9, 9, 4]? — David Knipe
– David Knipe, Commented Dec 24, 2017 at 12:44
Why do you convert your value to a number if you don't look for an index? — C.Champagne
– C.Champagne, Commented Dec 24, 2017 at 12:47

vibhor1997a · Accepted Answer · 2017-12-30 14:12:58Z

3

If the array contains number or string you can do something like this,

//Returns the first duplicate element   
function firstDup(arr) {
  let o = {}; //an empty object
  for (let i = 0; i < arr.length; i++) {
    if (o[arr[i]]) { //check if the property exists
      return arr[i];
    } else {
      o[arr[i]] = 'a'; //set the object's property to something non falsy
    }
  }
  return -1; //If No duplicate found return -1
}

console.log(firstDup([2, 3, 3, 1, 5, 2]));
console.log(firstDup([2, 4, 3, 5, 1]));

edited Dec 30, 2017 at 14:12

answered Dec 24, 2017 at 12:28

vibhor1997a

2,3862 gold badges19 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Jonas Wilms · Accepted Answer · 2017-12-30 17:12:58Z

2

function firstDuplicate(array) {
  const numbers = {};
  
  for (const number of array) {
    if (numbers[number]) {
      return number;
    } else {
      numbers[number] = true;
    }
  }
  
  return -1; // No duplicate
}

const duplicate = firstDuplicate([1, 2, 3, 4, 5, 6, 10, 1, 3]);
console.log(duplicate)

edited Dec 30, 2017 at 17:12

Jonas Wilms

139k20 gold badges164 silver badges164 bronze badges

answered Dec 24, 2017 at 12:46

codejockie

11.1k5 gold badges52 silver badges58 bronze badges

Comments

Jonas Wilms · Accepted Answer · 2017-12-30 17:12:12Z

1

You may instead use find and indexOf :

 function findFirstDupe(array) {
   return array.find((n, i) => array.indexOf(n) !== i);
 }

Or you use a Set to check for previous appearances:

function findFirstDupe(array){
  const set = new Set();
  return array.find(n => set.has(n) || (set.add(n), false));
}

The same with an object as a hash:

function findFirstDupe(array){
  const hash = {};
  return array.find(n => !(hash[n] = !hash[n]))
}

answered Dec 30, 2017 at 17:12

Jonas Wilms

139k20 gold badges164 silver badges164 bronze badges

Collectives™ on Stack Overflow

Decrease execution time of "firstDuplicate" algorithm

Examples

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

Examples

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related