Return the first duplicate number from an array

Question

I'm trying to solve a simple challenge where I write a function that returns the first duplicate number in an array.

This is what I tried:

function duplicateNumber(arr) {
    for (var i = 0; i < arr.length; i++) {
        for (var j = arr.length; j >= 0; j--) {
            if (arr[i] === arr[j]) {
                var dup_num = arr[i]
            }
        }
    }
    return dup_num
}

It doesn't seem to be working. What am I doing wrong?

Just realized I'm also looping from end to beginning and beginning to end.

in the array = [3, 5, 6, 8, 5, 3]

the duplicate number should be 5 since it's duplicated before 3.

Answer 1

In ES2015, it's really as easy as

let dupe = arr.find((k,i) => arr.lastIndexOf(k) !== i);

where you just check the index to see if there are indices with the same value before this one, and in that case, it would be the first found duplicate.

function duplicateNumber(arr) {
	return arr.find((k,i) => arr.indexOf(k) !==i);
}

console.log( duplicateNumber([3, 5, 6, 8, 5, 3]) ) // 5 (not 3)
console.log( duplicateNumber([1, 2, 3, 1, 2, 3]) ) // 1
console.log( duplicateNumber([1, 2, 3, 4, 4, 2]) ) // 4 (not 2)

Without ES2015

function duplicateNumber(arr) {
  var item = null;

  for (var i = 0; i < arr.length; i++) {
    if (arr.lastIndexOf(arr[i]) !== i) {
      item = arr[i];
      break;
    }
  }

  return item;
}

console.log(duplicateNumber([3, 5, 6, 8, 5, 3])) // 5
console.log(duplicateNumber([1, 2, 3, 1, 2, 3])) // 1
console.log(duplicateNumber([1, 2, 3, 4, 4])) // 4

Answer 2

You could iterate untile the element before the end and check against from i + 1 until the end.

This function returns the first duplicate only.

Fast version with one loop and a hash table.

function duplicateNumber(array) {
    var hash = Object.create(null),
        i, l, value;

    for (i = 0, l = array.length; i < l; i++) {
        value = array[i];
        if (hash[value]) {
            return value;
        }
        hash[value] = true;
    }
}

console.log(duplicateNumber([3, 5, 6, 8, 5, 3]));       // 5
console.log(duplicateNumber([0, 1, 2, 3, 4, 4, 5]));    // 4
console.log(duplicateNumber([0, 1, 1, 2, 3, 4, 4, 5])); // 1