find the first duplicate number from an array for which the second occurrence has the minimal index

Question

i am trying to write a javascript code to find the first duplicate number from an arrayn for which the second occurrence has the minimal index.I have already written the function and it works fine for almost all given arrays except for the test case given below.

Input: a: [1, 1, 2, 2, 1] Output: 2 Expected Output: 1

The javascript code is given below

function firstDuplicate(a) {

  var firstIndex = "";
  var isMatch = false;
  for (var i = 0; i <= a.length; i++) {
    for (var j = i + 1; j <= a.length; j++) {
      alert(a[i] + "," + a[j]);
      if (a[i] === a[j]) {
        firstIndex = j;
        isMatch = true;
        break;
      }
    }


  }
  if (isMatch)
    return a[firstIndex];
  else
    return -1;

}

the program is bugged using alert statement inside the second for loop.I found that the value of a[i] and a[j] is same in the first execution of the loop itself yet the if condition right below fails. I wonder how this happens and can anyone plaese explain me why this happens?

Answer 1

You should only set firstIndex if it is lower than its current value.

Also, your loop bounds are incorrect. They should have < instead of <=.

console.log(firstDuplicate([1, 1, 2, 2, 1])); // 1
console.log(firstDuplicate([2, 3, 3, 1, 5, 2])); // 3
console.log(firstDuplicate([2, 4, 3, 5, 1])); // -1

function firstDuplicate(a) {
  var firstIndex = Infinity;
  var isMatch = false;
  for (var i = 0; i < a.length; i++) {
    for (var j = i + 1; j < a.length; j++) {
      // ---------------vvvvvvvvvvvvvvvvv
      if (a[i] === a[j] && j < firstIndex) {
        firstIndex = j;
        isMatch = true;
        break;
      }
    }
  }
  if (isMatch)
    return a[firstIndex];
  else
    return -1;
}

---

Here's another way to write it:

console.log(firstDuplicate([1, 1, 2, 2, 1])); // 1
console.log(firstDuplicate([2, 3, 3, 1, 5, 2])); // 3
console.log(firstDuplicate([2, 4, 3, 5, 1])); // -1

function firstDuplicate(a) {
  let idx = Infinity;
  for (const [i, n] of a.entries()) {
    const dupIdx = a.indexOf(n, i+1);
    if (dupIdx !== -1 && dupIdx < idx) {
      idx = dupIdx;
    }
  }
  return isFinite(idx) ? a[idx] : -1;
}

Answer 2

You could take a single loop approach with using a hash table for indicating visited items.

function firstDuplicate(array) {
    var hash = Object.create(null),
        i = 0,
        l = array.length,
        item;

    while (i < l) {
        item = array[i];
        if (hash[item]) {
            return item;
        }
        hash[item] = true;
        i++;
    }
    return -1;
}

console.log(firstDuplicate([1, 1, 2, 2, 1]));    //  1
console.log(firstDuplicate([2, 3, 3, 1, 5, 2])); //  3
console.log(firstDuplicate([2, 4, 3, 5, 1]));    // -1

Answer 3

Solution in Javascript:

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

console.log(solution([2, 1, 3, 5, 3, 2])); // 3
console.log(solution([2, 2])); // 2
console.log(solution([2, 4, 3, 5, 1])); // -1