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

Answer 3

Your inner loop traverses down to 0. Instead it should only go down to i+1 so that it doesn't run into the current character in the outer loop, making it think it found a duplicate.

Also, your inner loop should start at arr.length-1 to be correct so that it's not testing an out-of-bounds index.

Code has been updated to reflect changes in the question

function duplicateNumber(arr) {
  var idx = arr.length;

  OUTER:
  for (var i = 0; i < idx; i++) {
    for (var j = idx-1; j >= i+1; j--) {
      if (arr[i] === arr[j]) {
        idx = j
        continue OUTER
      }
    }
  }
  return arr[idx]
}

console.log(duplicateNumber([3, 5, 6, 8, 5, 3]));

I also returned immediately when the duplicate was found, since there's no reason to continue looping should stop at that point so that you don't overwrite your result with a later duplicate.

If no duplicate is found, it returns undefined.

---

With the updated requirements, we store the index of the duplicated index, and continue on. If another duplicate is found it replaces the currently stored one.

The inner loop always starts at the index before the last found index, and traverses down to i+1, since we don't care about index above the last one found.

Answer 4

You don't need a second loop, you could use Array.prototype.indexOf(). Also, you could reduce lines of code and return the result at once. For example:

function duplicateNumber(arr) {
  for (var i = 0; i < arr.length; i++) {
    if (arr.indexOf(arr[i]) !== i) {
      return arr[i];
    }
  }
  return null;
}

console.log(duplicateNumber([3, 5, 6, 8, 5, 3]));

Answer 5

function getFirstDupe(arr){
  var dupe;

  if(arr && arr.forEach){
    arr.forEach(function(item, index){
      if(dupe === undefined && arr.indexOf(item) !== index){
        dupe = item;
      }
    })
  }

  return dupe;
}

Answer 6

just an alternative approach, you can use an object to store the count

function duplicateNumber(arr) {
    let count = {};
    for (var i = 0; i < arr.length; i++) {
        count[arr[i]] = (count[arr[i]] || 0) + 1;
        if(count[arr[i]] > 1){
            return arr[i];
        }
    }
    return dup_num
}

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

Answer 7

If you want this in the shortest amount of time. I would suggest things like this. This will complete in worst case O(n);

function duplicateNumber(arr) {
  var memory = {};
  for (var i = 0; i < arr.length; i++) {
    if(memory[arr[i]] === undefined){
      memory[arr[i]] = true;
    }else{
      return arr[i]
    }
  }
}

var arr = [2,3,2,3];
console.log(duplicateNumber(arr));

Answer 8

To elaborate on what spanky said: With your solution, you will at one point always end up comparing arr[i] with arr[j] while i being equal to j (therefore to itself). And because you don't stop your iteration when you find a match, my guess is that your function will always return the last element of your input array.

Answer 9

const solution = arr => {
const duplicates = ar => ar.filter((item, index) => ar.indexOf(item) !== index)
if (duplicates(arr)[0]) return duplicates(a)[0]
else return -1
}

First, filter out the duplicates by their indices then return the index 0 of arr.