Finding First Duplicate In An Array And Returning The Minimal Index

So the question reads: 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

Solution 1:

you can keep adding numbers to a dictionary as keys with values as their index, and as soon as you find a repeating key in the dictionary return its value. This will be O(n) time complexity and O(n) space complexity.

functionfirstDuplicate(arr) {
  var dictionary = {};

  for(var i = 0; i < arr.length; i++) {
if(dictionary[arr[i]] !== undefined)
     return arr[i];
else
   dictionary[arr[i]] = i;
  }

  return -1;
}

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

Since the numbers are between 1 to arr.length you can iterate on the array. For each arr[i] use arr[i] as index and make the element present and arr[arr[i]] negative, then the first arr[arr[i]] negative return arr[i]. This give O(1) space complexity and O(n) time complexity you can do this:

functionfirstDuplicate(arr) {

  for(var i = 0; i < arr.length; i++) {
if(arr[Math.abs(arr[i])] < 0)
     returnMath.abs(arr[i]);
else
   arr[Math.abs(arr[i])] = 0 - arr[Math.abs(arr[i])];
  }

  return -1;
}

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

Solution 2:

functionfirstDuplicate(arr) {
   for(var i = 0; i < arr.length; i++) {
        var num = Math.abs(arr[i]);
        if(arr[num] < 0)
            return num;
        arr[num] = - arr[num];
    }
    return -1;
} 
console.log(firstDuplicate([2,2,3,1,2]));

Solution 3:

functionfirstDuplicate(arr) {
    var numMap = {};
    for (var i = 0; i < arr.length; i++) {
        if (numMap[arr[i]]) {
            return arr[i];
        }
        numMap[arr[i]] = true;
    }
    return -1;
}

Solution 4:

Answer mentioned by @dij is great, but will fail for [2,2] or [2,3,3], a little change for input [2,2], i=0 we get a[ Math.abs[a[0] ] = a[2] = undefined so we remove 1 from a[ Math.abs[a[0] -1 ] this will work now

functionfirstDuplicate(arr) {

  for(var i = 0; i < arr.length; i++) {
    if(arr[Math.abs(arr[i])-1] < 0)
      returnMath.abs(arr[i]);
    else
      arr[Math.abs(arr[i])-1] = 0 - arr[Math.abs(arr[i])-1];
   }

   return -1;
}

Solution 5:

Please try the code below:

functiongetCountOccurence(A) {

    let result = [];
    A.forEach(elem => {
        if (result.length > 0) {
            let isOccure = false;
            result.some((element) => {
                if (element.element == elem) {
                    element.count++;
                    isOccure = true;
                }
            });
            if (!isOccure) {
                result.push({element: elem, count: 1});
            }
        } else {
            result.push({element: elem, count: 1});
        }
    });
    return result;
}

functiongetFirstRepeatingElement(A) {

    let array = getCountOccurence(A);
    array.some((element)=> {
        if (element.count > 1) {
            result = element.element;
            returntrue;
        }
    });
    return result;
}